Solution:
Temporary fix without touching the core: disable the 404 handling for paged urls via filter pre_handle_404
in your theme’s functions.php:
function pre_handle_404($preempt, $wp_query)
{
if (isset($wp_query->query['page']) && $wp_query->query['page']) {
return true;
}
return $preempt;
}
add_filter( 'pre_handle_404', 'pre_handle_404', 10, 2 );