Cannot open any Office 2013 application after Windows 10 1803 update

The latest Windows 10 feature update has somehow corrupted my Office Home and Business 2013 installation.

I cannot run any of the applications. I get the flashy popup from Office, stating that "Something went wrong" and suggesting going to Apps & Features to use the Repair option. Using Apps & Features > Microsoft Office Home and Business 2013 - en - us > Modify has no effect at all (probably crashes as well).

Here are some events from EventViewer, which are probably related:

Faulting application name: OfficeClickToRun.exe, version: 15.0.4997.1000, time stamp: 0x5a2f8608
Faulting module name: ntdll.dll, version: 10.0.17134.1, time stamp: 0x207580e2
Exception code: 0xc0000005
Fault offset: 0x000000000000820c
Faulting process id: 0xf9c
Faulting application start time: 0x01d3fbe104d1365f
Faulting application path: C:\Program Files\Microsoft Office 15\ClientX64\OfficeClickToRun.exe
Faulting module path: C:\WINDOWS\SYSTEM32\ntdll.dll
Report Id: 3b36faf2-a13a-4559-b04f-a949cfc9e400
Faulting package full name: 
Faulting package-relative application ID:

Faulting application name: OfficeClickToRun.exe, version: 15.0.4997.1000, time stamp: 0x5a2f8608
Faulting module name: combase.dll, version: 10.0.17134.1, time stamp: 0xe818752e
Exception code: 0xc0000005
Fault offset: 0x000000000009952c
Faulting process id: 0xf9c
Faulting application start time: 0x01d3fbe104d1365f
Faulting application path: C:\Program Files\Microsoft Office 15\ClientX64\OfficeClickToRun.exe
Faulting module path: C:\WINDOWS\System32\combase.dll
Report Id: d090239d-92d7-4ccd-8449-cc74b4508160
Faulting package full name: 
Faulting package-relative application ID: 

The Microsoft Office ClickToRun Service service terminated with the following error: 
%%30038

There are also a few other similar entries. Trying to manually start above service gives "Error 30038: 0x7556".

I would have expected a ton of angry users with the same problem, but I had a hard time trying to find this specific issue online. I actually managed to get Outlook and Word to run once - there were also popups about activating Office. It is now dead completely.

Turns out I cannot even run the uninstaller from Apps & Features for Office. I get prompted by UAC after which nothing happens.

Can anyone shed some light on this?

This was painful. I was unable to uninstall Office through normal means and was also unable to re-install trough an installer for Office 2013, which I downloaded from official web pages. Similar symptoms as described in the question - the uninstaller/installer would kick off, but nothing would end up happening. Entering Windows 10 safe mode did not achieve anything.

I finally found something that worked in form of an additional tool provided by Microsoft (an "easy fix button"). This uninstalled Office and all of its components.

Afterwards I was able to install the suite anew.

I'm just going to add that requiring a specific service to be running in order to uninstall/repair any program is beyond comprehension.