Tried all the suggested fixes (and then some). No joy. Finally I downloaded the full file update Service Pack 1 for Microsoft Office 2013 (KB2817430) 32-Bit Edition. When I ran it, I got the same error as from Microsoft Update.
But now I could see the detailed log file that it left in my TEMP\System directory. And there was the root cause: "Error 1920.Service 'Windows Font Cache Service' (FontCache) failed to start". Which was true, I had (during some previous debugging session) set the Startup to "Disabled". Quick change to "Automatic" and "Start" and now the update worked like a champ.
I wonder how many other people struggle with a Windows/Microsoft Update error that gives you no real clue as to the root cause? And why can't Microsoft make it easier to see the detailed logs?