I've had this problem off and on for years, I just bought a new laptop to replace one that died after 8 years. I hoped the problem would go away with the new laptop, but it looks like it is associated with my login. I again went through all of the steps that are proposed everywhere (occasionally worked in the past only to come again). Didn't work, so I gave up. I was doing some speed tests with my new laptop and , while on OOKLA, I noticed they offered a desktop version. It was through the Store so I figured I was out of luck, but I tried anyway. It worked. The link took me to the Store where it recognized me and I got the app. I decided to try to get some other apps and it worked for those too. Later I went back to the OOKLA speed test to see it it would take me back there. It did.
So, if you can't solve this problem and get really frustrated, find a site that has a link to the Store and it might work for you. I'll use OOKLA when I need something, but others will probably work.
BTW, I still get the 0x80131500 error if go go directly to the store.