Ok, even weirder. When doing a new Steam install on my SSD (C:\) (not using it normally due to low space) then the game will start!

After trying to move the game to another Steam installation I now get an error message compared to nothing earlier. When starting the game in Steam a pop-up window with "Take On Mars" in the header, says "Steam must be running to play this game.".

Well, Steam is running...