Correct, で is used because it's giving context to a transitive verb.

AでBをC
C is the verb, B is the direct object the verb acted on, and A is either the place it happened, or another object that was used to perform C.
e.g. 箸で寿司を食べます (I eat sushi with chopsticks).
or レストランで寿司を食べます (I eat sushi at a restaurant).

That example applies to transitive verbs that need a direct object, i.e. use the を particle. With intransitive verbs に can be used. To take an example from an earlier lesson:
山に登りました ("I climbed the mountain," or more literally, "at the mountain, I ascended").

I think using に for this question would imply that you lost the wallet "at" the store in the same way you would throw a ball "at" a wall, which doesn't make sense. It would be used in different contexts like
e.g. 田中さんに花をあげます (I give flowers to Mr Tanaka)

That's the only situation I can think of in which you wouldn't put お in front. Don't think I've ever seen 店 used without the お until this sentence here.