I gave up. I formatted C:\ on my brand new ASUS M31AD (with Aus bloatware) took the Windows 8.1 Pro installation (as a MAPS-member I have this available) and started the virgin installation of W8.1 which (suprisingly) took me less than 10 minutes. After installation I first executed all updates (done within 15mins incl. the downloading), installed StarDock Start8 (to get rid of Metro as much as possible), installed Office 2013 and now after roughly 1 hour I am completely back to live with an UP-TO-DATE PC including this tedious update.
Who's to blame? I think partially Microsoft but also Asus who delivers a PC which apparently is not 100% conform MS-specs. The main problem in my case was a too small System Reserved partition which I could not increase with the recommended tools (like EASEUS partition magic).
Anyway: my advise when buying a new laptop/pc: delete the OEM-Windows installation and do a fresh complete Windows installation!