Custom post type pagination using natural query

I’m trying to list my custom posts without a manual query. My custom type is ‘product’ and this is the code I am using to get a ‘page’ that lists my products, based on rewrite slug defined for the post type (something like ‘store’)

// flush rules to get it working
function mss_rewrites($wp_rewrite) {
  global $wp_post_types;
  try { $slug = $wp_post_types['product']->rewrite['slug']; }
  catch(Exception $e) { return; }
  $newrules = array(
    $slug.'/?$' => 'index.php?post_type=product',
  );
  $wp_rewrite->rules = $newrules + $wp_rewrite->rules;
}
add_filter('generate_rewrite_rules', 'mss_rewrites');

It works perfectly:
http://mysite.com/store/product-x/ shows product X
http://mysite.com/store/ lists all products, respecting the limits, all is ok, but..
http://mysite.com/store/page/2/ shows the first page again
then I tried http://mysite.com/store/?paged=2, http://mysite.com/?post_type=product&paged=2 and both URLs are resolved in http://mysite.com/store/page/2/ and shows the first page again.

Yes, I can do my own query…. but I would like to find a solution in this way.

Thanks for any help!