The more info being:
OK sounds easy - first tried turning on PAE and NX in the virtual box settings, rebooted and retried. But the same error occurs.
Quick google later and discovered it's connected to this Bug 11899 - CMPXCHG16B instruction is disabled by default. Enabled it for this VM:
vboxmanage setextradata "win8" VBoxInternal/CPUM/CMPXCHG16B 1
Also needed to enable 3D on the graphics card:
And then sucessfully installed the update: