Problem solved!
In the end it was a third party software called Cybereason Ransomefree v 2.2.5.1. On one PC I uninstalled and the updates and store started working again. On the other PC I updated Ransomefree to **v 2.3.0.**0 and it solved the problem.
Thanks to Erik from Superuser from coming up with the answer.
So mark this as solved. :)