Windows Firewall is blocking Windows Update
I've found solution.
I found it here.
Essentially I added a new incoming rule which allowed all connections coming from c:\windows\System32\svchost.exe.
I wonder why my default settings didn't already have this? Anyway it worked!
In Win 8 Go to Control Panel>Firewall>Advanced Settings. Then click Action>Export policy to make a copy of your current policy in case you want to restore it. Then click Action>New Rule>Custom>Next in the Program step of New Outbound Rule Wizard under the Service heading select Customize>Apply to this service>Windows Update>OK
Optional: Program: select "this program path" and select the program c:\windows\System32\svchost.exe press ok
Optional: Protocol and Ports: specify tcp port 443
Allow this connection; select your profile or leave as is (it should be explained in the wizard pretty well); give it a name; finish