I have Windows 10 Build 1809 and use my Microsoft account to log in to my laptop. No sure when this started to happen. It's been probably about a month or so now. Whenever I opened Microsoft Store, it asked me to "Try that again" or "Check your connection" with an error code, 0x80131500 even though I was connected to the Internet. I tried everything I found online, SCAN, DSIM, WSReset, app reset, and a bunch of other fixes to no avail. Everything else, such Windows apps or user-installed software, worked just fine.
As per someone's recommendation, I added a user in Family & other users-I don't have this person's sign-in information-Add a user without a Microsoft account. I log in to the new user and Microsoft Store was able to launched normally. But when I switched back to my regular account, the error remained. Any idea is welcome!