When I first downloaded the game, after trying to start the new game I saw a message about missing "Microsoft Visual C++ 2015". There was a link to straight download of the file "vc_redist.x64.exe". I downloaded it (even if my computer said I already had it), uninstalled and installed it again. But that didn't fix the problem - the window about missing thing still pop up during start of the game.
I fixed the problem, but the info given by the "game" itself was incomplete.
I've downloaded both files, available at Microsoft website, for Video C++ Redistributable for Visual Studio 2015. so:
vc_redist.x64.exe AND vc_redist.x86.exe (while Klei only leaded to one of them before). Unistalled both. Installed again. Restarted computer. Game works. Here is the link to them: https://www.microsoft.com/en-US/download/details.aspx?id=48145
Game showing an error while starting the new game