Custom rewrite causes 404 on pagination

If anyone still has this issue (this post is quite old), I found a very helpful snippet in this blog post: https://www.grzegorowski.com/wordpress-rewrite-rules

/**
 * Reprioritise pagination over displaying custom post type content
 */
add_action('init', function() {
  add_rewrite_rule('(.?.+?)/page/?([0-9]{1,})/?$', 'index.php?pagename=$matches[1]&paged=$matches[2]', 'top');
});

This will ensure WP uses the pagination rule prior to the post type query rules