Orphan registry entries don't generally 'slow your computer down", but there are a bunch of companies that make money (adware or paid products) convincing you that they do!
Best things to speed up a slowing computer are (not necessarily all at once):
- SSD Disk
- more memory
- uninstall non-essential apps
- switch antivirus/antimalware vendors
Not sure if the store apps are completely removed on uninstall. They might store settings in the cloud, so you can share settings between devices, or so you dont lose in-app purchases if you uninstall/reinstall them.