Pagination not working in custom post type. Help

You shouldn’t be using new WP_Query() in archive-product.php (or any archive template). The right posts have already been queried, and this is what the pagination is based on. You just need to loop through the right posts with the standard loop. Look at the default archive template in WooCommerce:

while ( have_posts() ) {
        the_post();

        // etc.
    }
}

Notice that there’s no $the_query or anything like that.