PC APP STORE is usually installed alongside AUTO APP UPDATER (which both need to be removed). PC APP STORE is not always installed as an app that can be removed using ADD/REMOVE programs. Many time it is installed as a standalone app that is maliciously added to your startup routine (which accounts for why it shows up regardless of the browser you're using). Here is how to check if it is installed this way and how to remove it if it is:
1. CTL-ALT-DELETE and select task manager or run taskmgr from the run command.
2. On the left side of the screen you will see what looks like a speedometer dial (4th icon from the top). If you hover your mouse over each icon you will eventually see Startup apps. Select this icon.
3. Scan until you see PC APP STORE (if you don't see it it isn't running during startup).
4. If (under the status column) you see Enabled then continue if you see disabled you won't have PC APP STORE running on your PC.
5. Right click PC APP STORE and select DISABLE.
6. Scan to the top of the list and see if AUTO APP UPDATER is listed as well and disable that app.
7. Exit the TASK Manager and reboot.
8. Once you have rebooted, open File Explorer and find the folder PCAPPSTORE. Delete it. Deleting it will also delete AUTO APP UPDATER.