Pagination with custom post types results in 404 issues

By the time you reach the template, WordPress has already queried the database and decided what to display based on those results.

You’re seeing a 404 error because based on the default main query, there are no more posts to show.

When you call query_posts in the template, you overwrite that original query. Despite the fact that your new query results contain more posts, WordPress has no awareness of this modified query.

This is why you should never use query_posts in the template. You’ve provided the solution to your issue already, use the pre_get_posts action to modify the main query before it happens.