Google Play Games doesn't restore highscores? Maybe this question is totally dumb, but I was always under the assumption that if I connect a game with my Google Play account (if that's offered), my highscores, progress in games, etc. will be saved and restored if I connect it on another device or re-flash the phone's ROM?

However, with many games (like HexaBlast, Lara Croft, Temple Run etc.), no game stats and levels seem to get saved, I'm starting from point zero.

If Google Play Games isn't good for that, what's the actual point of connecting a game to Google Play Games at all?
Google Play Games Services support saving game progress since the beginning, and it's upgraded on November 2014. From Android Developer blogs,

[...], when Google Play Games launched, one of the very first features we included was the ability for users to save their game to the cloud [...]
[...] this past year (ed. 2014) at Google I/O, we launched an entirely new Saved Games feature, powered by Google Drive.

However, being able to save doesn't mean it will automatically save your game progress: the developer has to implement the logic that uses this service.
Anecdotally, I have played some (rhythm) games that use this service and worked properly when I replaced my Nexus 4 with Nexus 5. On your case, unfortunately, I have to say that this is fully the developers' fault.
As for why they use Google Play Games service, its features are not only for saving games: achievements, global highscores, etc.