Pagination for category slug returns 404 when page >= 2

I got fix this problem with:

add_rewrite_rule('blog/([^/]*)/page/([0-9]+)?/?$', 'index.php?post_type=blog&blogs_tax=$matches[1]&paged=$matches[2]', 'top');

In functions.php, after register_post_type.

Very important: You must flush rules. It is easy to do changing the permalink.