How to properly rewrite pagination rules for a CPT to avoid 404 error on /page/2

You don’t need the rewrite rules, and that’s not how they’d work anyway.

The fundamental problem is that you decided not to modify the main query, but to replace it.

There’s no need for the custom WP_Query or custom pagination, or a page template. Not to mention by running the main query then discarding the result to make a new one, it doubled the amount of work that needs doing, a major performance hit/slowdown

You can just use an archive-news.php template with a standard post loop, then use pre_get_posts to change how many posts are shown on the page:

// only show 4 posts per page on the news archive
add_action(
    'pre_get_posts',
    function( \WP_Query $query ) {
        // we only want the news post archive, exit early if it isn't
        if ( ! $query->is_main_query() || ! $query->is_post_type_archive( 'news' ) ) {
            return;
        }
        $query->set( 'posts_per_page', 4 );
    }
);

Now the news archive will show 4 posts per page. No rewrite rules, no CPT adjustments, no special page with a page template for the pagination, it should all just work out the box with that hook. You can use normal standard main loops like the default themes. It’ll even be faster! You’re no longer doubling up all the queries by discarding the main query and putting your own in.

With that, your above code can be simplified to this in an archive-news.php template:

while ( have_posts() ) {
    the_post();
    <!-- ECHOING THE NEWS POSTS-->
}

echo '<div class="pagination">';
echo paginate_links();
echo '</div>';