In my case I could see that MSVCP140_APP.dll was being loaded from the wrong path:
C:\Program Files\WindowsApps\Microsoft.VCLibs.140.00_14.0.32530.0_x64__8wekyb3d8bbwe\msvcp140_app.dll
I used Process Monitor to examine StartMenuExperienceHost.exe and saw it loading this:
C:\Program Files\Citrix\HDX\bin\Citrix.Hooking.Uwp.Bridge.dll
It's because I'm remoting to my desktop PC using Citrix, and more research lead me here:
https://support.citrix.com/s/article/CTX107825-how-to-disable-citrix-api-hooks-on-a-perapplication-basis?language=en_US
So I used this command to set the registry entry and disable it, and the problem was resolved immediate (no need for a restart):
reg add HKLM\SOFTWARE\Citrix\CtxHook /f /v ExcludedImageNames /d StartMenuExperienceHost.exe
I imagine the same issue might happen from other applications injecting themselves into StartMenuExperienceHost.exe though.
For reference, it used this DLL when successfully launching:
C:\Windows\SystemApps\MicrosoftWindows.Client.FileExp_cw5n1h2txyewy\msvcp140_app.dll