After troubleshooting with Process Monitor, Minecraft launcher is unable to locate the registry key HKLM\Software\JavaSoft\Java Runtime Environment\1.7.0_45\JavaHome. Creating a new registry key type String with the name JavaHome, I entered the value C:\Program Files\Java\jre7 which is the location of my Java installation. Minecraft was able to start there afterwards.
This issue may be with Java not installing the correct registry key in Windows 8.1 rather than Minecraft launcher not finding the key.
I too upgraded to Windows 8.1. The minecraft launcher is most insistent to install Java even though I have reinstalled the component several times. Launching the minecraft launcher with administrative privileges results in the same issue.
Running Windows 8.1 Pro x64
Java 1.7.45 update
Confirmed for 1.9.4