You also need to make sure that the Random Products module in its settings is set to appear on all pages in the Joomla menu assignment - otherwise Joomla will not allow it to appear regardless of what settings you choose in the VM Modcontroller.
If that does not solve your problem you should check that the page being displayed as your shop front page actually is the shop.index page, it is not obvious from your site whether it is that or not. It may be a category browse page, in which case you should add 'shop.browse' to the list of pages selected on the VM Page Parameter.
If you want it to display on a product details page then add shop.product_details as well. De-select the flypage.tpl selection from the Flypage parameter. You only need to use that if you only want to display on one particular type of flypage.
At the moment you are seeing the Random Products title being displayed on all your pages. You can turn that off by turning off the title display in the Random Products module settings. Alternatively uploading the modules.php file may solve that, as described in the documentation.