You can use tools like sh404 or ArtioSEF for this. They work with VM too.
As to the error, better double check the .htaccess (and try what is coming up when you deactivate the Ajax function in the VM admin). Do not use the standard SEF tools, use the mentioned ones. There are no issues to use VM with SEF on, but there are some modifications needed. The best is always to hire a pro to adjust those, as those can vary from site to site and modifications done by yourself. Afterwards, also the VM will work without problems with SEF on. Do not build on the stuff in the VM Forum, they have no idea themselves what is possible with VirtueMart.
This would be the best way, hire a pro!