Zend certified PHP/Magento developer

How to fix extremely slow Microsoft Store downloads?

I recently helped set up a new computer with Windows 11 (preinstalled), and while it went rather smoothly, there’s the problem that the Microsoft Store is downloading and installing extremely slow: It takes forever for any download or update to start, the download itself is painfully slow (as in sub-kb/s-slow, or no progress at all), and even after the download is completed, the actual installation/update also takes very long. There is no indication what the program is doing all that time, and no significant CPU or network activity, neither from the app itself not from other apps. For all other matters, the download-speed of the computer is fine.

This seems to be a common problem, even mentioned several times in the app’s own reviews in the Microsoft Store itself. But while there are countless guides on the net, I could not find any solution that works in my case, and no related question here. I tried, among others, all the steps here, but none of those made a difference. Those include, e.g., using the Windows Troubleshooter, “Repairing” or “Resetting” the App, deactivating download limiters or Antivirus (temporarily), and clearing different Cache directories. The situation was the same each time I tried over a course of several weeks, so I’d also rule out a temporary server problem.

So my question is: Is there anything else I can try besides the steps mentioned in the above article and elsewhere? Or should those definitely work and I must have been doing something wrong? If there is no fix, is there another way to update the builtin Microsoft utility apps? (Some just refuse to start before updates are installed.)