No solutions yet. I have upgraded Windows to version 17672.1000, and tried uninstalling and re-installing Office 2016 (64-bit) completely again. No luck. All office applications still say "The application was unable to start correctly (0xc000142)" on launch.
I tried installing the 32-bit version of Office as well; that did not work either.
Microsoft, I'm completely out of luck here. Is my only choice to start over and completely reinstall Windows?