I had that problem for months. Turns out "my" XBOX profile was set to not allow anything to be downloaded.
I never used any xbox or any profile connected to xbox. I tried everything, and reinstalled more times than I can remember - with and without downloading settings. It was only because some app finally threw up an error that was different from the "Something went wrong on our end - please try again in a few minutes" error I had gotten till then.
Edit:
Come to think of it, I could download apps I already owned from "my library" in the store. So I could download some apps. It was just anything I hadn't downloaded before I couldn't download. I bumped into this problem with a new computer, and when Edge began to support adblock and other plugins, I was bummed that I couldn't download anything new from the store.