you formulate some interesting requirements. I think the crux of the matter is the nature of the interaction between clients, in-shop services and central server, not so much the discovery aspect of it.
I believe that whether that interaction is by webservices or REST is, at this stage, irrelevant. (In general, don't be intimidated by SOAP: support for it on all relevant platforms is near-optimal and it's perfectly easy to use.) Just stay away from UDDI, if that is what you've had in mind when you said "SOAP includes a discovery protocol".
I'd focus on the following questions first (just sketching here in the hope that it might be useful):
1. Is the deployment/roll-out/maintenance of rich client apps at end-user machines (PCs and tables) likely to be a problem? If so, then i'd stick with a pure web frontend. I'll assume this to be the case.
2. What proportion of the interaction is with in-shop vs. central services? How many use cases need central vs. in-shop vs. both services, and how will these be distributed at runtime (i.e., which servers will be hit most). Do the stores have the IT capabilities to maintain their (presumably crucial) in-store services in a reliable fashion (or should as much as possible be hosted centrally and hence reliably)?
3. What is the exact difference between in-shop services at different shops?: Just the location (hostname, IP) of the servers, or (also) their implementation (logic or even language), or (also) their interface (as expressed by a WSDL or REST contract), or (also) how many and what kinds of services are available at what shop? That's crucial, i'd think, and will determine how you tie these in-shop services together into one application. Somehow i can't believe that you'll get by without some store-specific configuration. But, if all stores are expected to run the same services with the same interface at the same port, just at different machines, then a common set of hostnames (as suggested by Kevin) for all stores is a nice, simple solution.
4. Depending on the above, one straightforward architecture could be for each store to host their own appserver and webapp, with each client in that store being just a browser connecting to only that one webapp. That in-store webapp would then need to be configured (or coded to discover) all in-store services and call out to them when needed (intra-store calls). Similarly, the in-store webapp could also call the central server if and when needed - the central server would just be another service (irrelevant if SOAP or REST). In that model, authentication of end-users by the webapp could be done by an in-shop service (against an in-house user store) or a central service (against a central user store that knows all users in all stores) - which is probably also an important question.
The only way to decide this rationally is to think through the exact nature of the dependency and interaction (static and dynamic) between central and in-house resources, request throughput, IT capabilities in the shops, and the like.
I hope i've not missed the nature of your question.