I have discovered the cause of the problem by looking at the failed install logs and doing some internet research.
My HP Elite 7500 computer has the Windows 8 key in its UEFI BIOS.
When Windows 8.1 update is run from the App Store the 0x80004005 error is caused because the Windows 8 Pro key that HP have in the UEFI BIOS doesn't pass the key check test.
The Windows 8 key in the HP UEFI BIOS is obviously useful when reinstalling Windows 8 Pro from the recovery partition because it is automatically inserted in the installer so you don't have a sticker on the side of the case and don't have to type it in.
However, not only does the Windows 8 Installer automatically read this key, but so does the Windows 8.1 ISO updater -- it's automatically inserted and fails test.
So there is no way to update my HP Elite 7500 computer to Windows 8.1 or Windows 8.1 Update 1 because the key is in the UEFI BIOS and cannot be bypassed.
What's worse is that HP's webpages say they have no plans to support Windows 8.1 on this hardware; so my year old computer will no longer receive updates and support.