Worked great!

This solved the issue with the custom permalink structure & pagination links like working (ex: https://www.mysite.com/category/page/2). The links are properly working now.

This plugin basically just contains two small functions. I just added these to my functions.php file in my theme folder, so no need to run an additional plugin.

ADDED:
I put this little function together that will additionally allow you to change the number of posts per page for “categories”. You could change this for other types of archive pages. This simple function can be added to your theme’s functions.php file.

function category_posts_per_page( $query ) {
    if ( $query->is_category() && $query->is_main_query() ) {
        $query->set( 'posts_per_page', 3 );
    }
}
add_action( 'pre_get_posts', 'category_posts_per_page' );