I've got the same problem as yours, and I tried everything. Rebooting, use the MS tool to fix store problems, I even 'refreshed' the surface (RT 1st gen for me) but with the option to keep all the files and settings. No luck.
Then I created a new local dummy user account on the surface and the store was loading... But only for that user, not for me.
So I decided to backup everything in One Drive, and restore my surface from scratch... At the restore window, I chose to start without a previous backup and setup like a new device.
Now the store is loading properly. Sadly I have not found any other solution