Can I remove Windows App Store from Windows 8.1?

I am sure you figured this out by now, but seeing as you haven't given this question an check mark for correct answer I am giving you my two cents.

First stop the service named:

1. Go to Services
2. Find the service called: Display Name: Windows Store Service(WSService)
3. Run "remove-appxpackage Winstore's ID"

This should remove the application, but only once the service is stopped. If you cannot find the service in Services, go find it in the registry. The registry name is: Service Name (registry): WSService

Let me know if this helps you a year and a half later. For future reference all applications running a services most likely need that service stopped before a remove is possible.

The UnderDog

You should be able to remove the Winstore in the context of the machine, rather than the user (which is implied by the error message). I have met with success removing Group Policy (which also insists that it is a part of Windows) by using a Task Scheduler task (running as LOCALSYSTEM) to stop the service and then remove it.

Since the Winstore is a Windows Service, this solution should work for you.