Permalink/Pagination issue: Category base name same as page name

This is untested, but should work for you. Visit the permalinks settings page to flush rewrite rules after adding:

function wpa_fix_blog_pagination(){
    add_rewrite_rule(
        'blog/page/([0-9]+)/?$',
        'index.php?pagename=blog&paged=$matches[1]',
        'top'
    );
}
add_action( 'init', 'wpa_fix_blog_pagination' );