I recently had a site with a custom post type and the pagination was not working because the post type slug was the same as the page slug (news and news).
I wasn’t using the archive page to display the post loop so I disabled the post type archive in the file I initiated the custom post type:
register_post_type( 'news',
array(
[...]
'has_archive' => false,
[...]
)
);
And then I added this rewrite to functions.php:
// prioritize 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'
);
});