API pagination with external or centralised authorization

For an efficient solution you need to be able to put the authorization and pagination constraints into the database query, and have the proper indexes for those aspects. Anything else will potentially overfetch an enormous amount of data. How big an issue this is depends entirely on the scale and characteristics of your data.

Can you translate the information you get from the authorization layer into a filter on the database query? Ideally something like getting the information "User A can access Projects X,Y and Z" and translate that into filters on your query.

If you cannot do that and have to pass every single result to it to know whether it is visible, you will always have some pathologically slow scenarios. For example if you have 1 million items, and your current user is allowed to view 10 of them, you might have to push the entire million items through the authorization layer just to get 10 results. How big of a problem this is depends heavily on the specifics of your application.

If you cannot push all these concerns to the datbase, which I assume is the case from your description, I think something like your solution 2 is the only reasonable way to handle this. You essentially need an internal pagination layer that fetches a bunch of results, passes them through the authorization layer and provides them to the rest of your application. Your externally-visible pagination layer then needs to request internally pages results until it has enough to fulfill the request.

This has the issue I mentioned above with potentially pathological queries in terms of performance, but I see no way to avoid that with these restrictions. There is also no fundamental issue with querying specific pages in this way, it's just expensive as you have to also query all pages before. But that is a general issue with pagination unless you can use advanced methods like keyset pagination.

If it is possible, you can also simply avoid providing the option to query specific pages. So you'd only provide a "next" link in each paginated response. This gives you the largest flexibility in designing your pagination, but obviously restricts what the client can do.