Yes, you should look to implement HTML 5 whenever it's 1.) a cost-effective decision to do so and 2.) your audience isn't plagued with non-compatible browser users, but not because it provides some secret sauce over previous versions.
As of today, it's very clear that HTML 5 is going to be the long-running standard as is shown by the
amount of support from the Google dev heads.
As far as SEO is concerned, HTML 5 doesn't communicate the content structure better, it just does so
differently. For example, in HTML 4, the <h1> tag communicates the overall topic of the page. In HTML 5, the <h1> tag applies specifically to sections of content. This means that our knee-jerk reaction to refrain from using too many <h1> tags might actually communicate our content inaccurately when Google crawls our pages in HTML 5.
View the changelog differences from HTML 4 to 5 here.
So if your answers to points 1 and 2 are yes, then a third question you should be asking is "is this theme using HTML 5 correctly?" Because that's probably the biggest downfall to HTML 5. While it's a relatively simple semantic for what an SEO wants to achieve, there are still people who don't understand how to use it correctly (think MLA/APA formatting, for the web).
When a new technology is introduced, it's generally good practice to stay away from using it in production until you start to see communities and other dependent tech start to adopt it. And even then, you've got to wait for old tech to phase out. I think 2013 is a good year to start the move towards HTML 5, but there are still plenty of cases where it doesn't matter immediately.
