Just want to share the results of a lot of troubleshooting on my part - I bought a new PC, came with Windows 8.1, installed Steam fine, downloaded DoW2R no problem, verified game cache no problem... game wouldn't start no matter what. Clicking "play" will result in the mouse pointer getting the spinning wheel for a bit... then nothing.
Solution: manually installing DirectX 9.0c worked for me. Downloaded the "web installer" off the official Microsoft download site. Apparently the version of DirectX that comes default on Windows 8 doesn't work with the game.