There's a bug report on Oracle's VirtualBox ticket system that seems to be caused by KB3004394. For some, uninstalling the update resolves the VirtualBox failures.
Had a look at the VirtualBox breakage.
The problem seems to be that the update does not install any catalog file C:\Windows\System32\CatRoot and it's therefore impossible to verify the new crypto32.dll file that the it installs. (Compare "sigcheck -i C:\Windows\System32\crypto32.dll" output before and after installing the update. Sigcheck says it's signed before and unsigned after.)
The Windows 8.1 version of the update works, i.e. installs C:\Windows\system32\CatRoot{F750E6C3-38EE-11D1-85E5-00C04FC295EE}\Package_1_for_KB3004394~31bf3856ad364e35~amd64~~6.3.1.0.cat that we (and sigcheck.exe from microsoft/sysinternals) can successfully validate the DLL. (I've only tried 64-bit Windows 8.1 and Windows 7, so I cannot tell exactly which updates are broken.)
The only way to make VirtualBox work again is reverting/removing the update, unless Microsoft fixes the missing .cat file issue. I sincerely hope that Microsoft will update the update with a working cat file eventually...
-bird
PS. Would be really swell if files like crypto32.dll and wintrust.dll had embedded signatures instead of only external ones. It would not only do away with these kind of issues but also make it a lot easier to verify that the files haven't been tampered with.