Custom post type and custom taxonomy 404 on page 2

So after many trials and errors, I found I had to create a specific rewrite rule to go into my functions.php, one that handles post type ‘videos‘ and the category (taxonomy) ‘videos_category‘:

add_filter('init', function() {
    add_rewrite_rule( 
        '^videos/([^/]*)/([^/]*)/(\d*)?',
        'index.php?videos_category=$matches[1]&p=$matches[2]&paged=$matches[3]',
        'top' 
     ); 
});

I also found this plugin to be really helpful for viewing my rewrite rules:
https://wordpress.org/plugins/rewrite-rules-inspector/