Q1. Which option (VPS or dedicated) seems to be the best to host moodle for this condition?
You should be OK with a decent VPS. I'm assuming that we are talking about Linux VPS. I don't know about Windows VPS.
Delivering videos (and other files) needs bandwidth, not CPU nor RAM. If you conduct synchronous on-line exams (using quizzes) only, depending on the number, size of the exam paper and how exactly synchronous - all in the same minute or distributed over 10 min. - you'll experience the limits of your machine.
By then, you should have found out how to do site backups, which you can easily migrate to a more powerful machine.
The costs of maintaining a server
application is not in the hardware, it is about user management, backup, availabilty, security, privacy, ...
Q2. Which Moodle version should I use for the first install?
The short answer is, if you have never used Moodle then you can start anywhere. Since 1.9 is the "old" version, better to start with a newer version, 2.2 or 2.3. Install one and test it!
But that is not the topic of this forum. If you want to discuss that further please visit a more suitable forum. People have discussed this in "Installation problems", "General problems", "Comparison and Adovacay", "General developer forum", ... You can use the 'Advanced search faciliy' mentioned in the introduction to this forum. The intro also has links to important technical documentation.