Slightly odd for us to posting this fix on our tech support KB for inkjet printers but it bears recording as it has been the bane of our lives for years now.
Symptoms:
Microsoft Store runs so slowly that you could be waiting weeks for it to complete download of any of the updates waiting on it.
Cause:
Gaming Services is stuck in a loop that is trying to update and failing causing it to block all other downloads from the store pretty much forever!
Fix:
Ref: https://superuser.com/a/1803813/1911148
We actually didn’t remove the XBox app, we just removed the gaming service using the Powershell script provided in the linked post above and immediately everything started downloading at normal speed. We did have to reinstall the Xbox app for a home machine so that Gaming services would download successfully (and Minecraft would install for our youngest) but it’s working.
All other workarounds involving resetting the MS Store system failed for us but are worth keeping in mind as a first port of call if you haven’t tried them already.