Error 80073712 = ERROR_SXS_COMPONENT_STORE_CORRUPT
I debugged this the last days several times. The fix is to run those 2 commands from a cmd, started as admincmd, started as admin:
32Bit Windows:
dism /online /remove-package /packagename:Package_for_KB2919355~31bf3856ad364e35~x86~~6.3.1.14
dism /online /cleanup-image /startcomponentcleanup
64Bit:
dism /online /remove-package /packagename:Package_for_KB2919355~31bf3856ad364e35~amd64~~6.3.1.14
dism /online /cleanup-image /startcomponentcleanup
reboot and try to install the Updates again.
When it still fails, you can use the new Refresh/Reset featureRefresh/Reset feature (which removes all desktop applications but repairs the Windows Core) or the old InPlace Upgrade to repair WindowsInPlace Upgrade to repair Windows completely. This also keeps all desktop applications.