Insert this in component/com_sh404sef/sef_ext/com_virtuemart.php just after the function definitions (eg: 
i.e. at around line 95):
// Detect where a menu item with a non-standard Itemid is being processed and simulate a VM internal 'menu' item to facilitate pagination
global $sess;
if( !isset($sess) ) {
 require_once( JPATH_ROOT.DS.'components'.DS.'com_virtuemart'.DS.'virtuemart_parser.php' );
}
$vm_Itemid = $sess->getShopItemid();
// Check whether the Itemid is the usual value for a VM menu item
if( $Itemid != $vm_Itemid ) {
 // The URL is based on a menu item other than the standard VM menu item (usually the home page)
 // VM always uses the standard VM Itemid value in pagination URLs and so this URL will be updated to
 // use the standard Itemid and to incorporate any menu item parameters, in case pagination is appropriate.
 $menu = & shRouter::shGetMenu();
 $menuItem = $menu->getItem( $Itemid );
 if( $menuItem ) {
  // Get the menu parameter set
  $menuparams =& new JParameter( $menuItem->params );
  // Replicate the logic used by VM to assess whether a browse or product detail page required
  $tmp_product_id = $menuparams->get( 'product_id' );
  $tmp_category_id = $menuparams->get( 'category_id' );
  // Get the page name and remove '.php', if present
  $tmp_page = preg_replace('/\.php/', '', strtolower($menuparams->get( 'page' )));
  if( !empty($tmp_product_id) ) {
   $default_page = 'shop.product_details';
  } else if( !empty($tmp_category_id) ) {
   $default_page = 'shop.browse';
  } else {
   $default_page = '';
  }
  $tmp_page = empty($tmp_page) ? $default_page : $tmp_page;
  // Check whether the menu item is a browse page or product detail page (other pages are excluded
  $allowed_pages = array(
       'shop.browse',
       'shop.product_details',
       );
  if( in_array($tmp_page, $allowed_pages) ) {
   // Clear down the unwanted get vars from the $shGETVars array
   $required_params = array(
         'option',
         'lang',
         );
   global $shGETVars;
   foreach( $shGETVars as $param ) {
    if( !in_array($param, $required_params) ) {
     unset($$param);
     unset($shGETVars[$param]);
    }
   }
   // Reset the Itemid
   $Itemid = $vm_Itemid;
   shAddToGETVarsList( 'Itemid', $Itemid );
   // Replicate the logic used by VM to include specific parameter values
   if( !empty($tmp_product_id) ) {
    $product_id = $tmp_product_id;
    shAddToGETVarsList( 'product_id', $product_id );
   } else if( !empty($tmp_category_id) ) {
    $category_id = $tmp_category_id;
    shAddToGETVarsList( 'category_id', $category_id );
   }
   
   $tmp_flypage = $menuparams->get('flypage');
   if( ( !empty($tmp_product_id) || !empty($tmp_category_id) ) && !empty($tmp_flypage) ) {
    $flypage = $tmp_flypage;
    shAddToGETVarsList( 'flypage', $flypage );
   }
   
   $page = $tmp_page;
   shAddToGETVarsList( 'page', $page );
 
   // Process any other menu parameters not already processed
   $params = $menuparams->toArray();
   // Exclude system parameters and those already processed
   $excluded_params = array(
         'product_id',
         'category_id',
         'flypage',
         'page',
         'page_title',
         'show_page_title',
         'pageclass_sfx',
         'menu_image',
         'secure',
         );
   // Process each parameter
   foreach( $params as $param => $value ) {
    if( !in_array($param, $excluded_params) && $value != '' ) { // Note empty() is not used here because zero is valid
     $$param = $value;
     shAddToGETVarsList( $param, $value );
     shRemoveFromGETVarsList( $param );
    }
   }
  }
 }
}
// Set the page number for browse pages, if not already set
if( !isset($limitstart) || !isset($limit) ) {
 $my_page = explode('.', $page);
 $pagename = isset($my_page[1]) ? $my_page[1] : '';
 if( $pagename == 'browse' ) {
  global $vm_mainframe, $mosConfig_list_limit;
  if( !isset($limitstart) ) {
   // VM stores a different default limitstart value for each different browse page. That value must be identified so that the URL
   // is created for the expected page
   // Store the 'current value' of limitstart so that it can be restored later
   $save_limitstart = vmRequest::getVar('limitstart');
   // Setting the 'current value' to null allows the stored value (if any) to be retrieved without it being overwritten by a
   // 'current value' that is usually not applicable to that particular browse page
   vmRequest::setVar( 'limitstart', null );
   // Force a consistent value for category_id when empty
   $category_id = empty($category_id) ? 0 : $category_id;
   $limitstart = (int)$vm_mainframe->getUserStateFromRequest( "view{$keyword}{$category_id}{$pagename}limitstart", 'limitstart', 0 );
   shAddToGETVarsList( 'limitstart', $limitstart );
   // Restore the original 'current value' of limitstart
   vmRequest::setVar( 'limitstart', $save_limitstart );
  }
  if( !isset($limit) ) {
   // No need to save and restore values here because VM only uses one value globally
   $limit = (int)$vm_mainframe->getUserStateFromRequest( "viewlistlimit{$page}", 'limit', $mosConfig_list_limit );
   shAddToGETVarsList( 'limit', $limit );
  }
 }
}
// Ensure that $limitstart is a multiple of $limit (this can occur if $limit was changed since $limitstart was set)
if( isset($limitstart) && $limit > 0 ) {
 $limitstart = floor($limitstart/$limit)*$limit;
 shAddToGETVarsList( 'limitstart', $limitstart );
}
In backend settings:
Look for Virtuemart configuration in plugins page
- Select to YES the option that says “Using Items per page drop-down list”
- Save your settings
- Purge SEF urls