My solution to make GamingServices update without an error (after I tried everything else). The problem is really that Windows supposes that the newer version of GamingServices is already installed (I could see it in Event Viewer). Don't ask why...
So:
Open Registry Editor
Go to HKEY_LOCAL_MACHINE -> SYSTEM -> CurrentControlSet -> Services
Remove the GamingServices and GamingServices.Net
Restart Computer
Go to your Windows Store -> 3-dot-menu -> Downloads and Updates -> Check updates
Gaming Services should install now without issue.
Double check by rebooting and going back to Windows Store and trying to Get Updates again - you should be Up to date.
Thanks to someone on the internet suggesting to take a look into Event Viewer to see what the error actually is. And shame on Microsoft for not being able to resolve the issue for such a long time, AND not to be able to actually show what exactly is the error in the user interface.