We can consult Japanese google for this:
Here’s one pretty thorough take: 屋と店 | ことば（放送用語） - ことばウラ・オモテ | NHK放送文化研究所
Overview:
- There is no hard and fast rule–just use precedent
- News and formal discussions tend to append 店 to more sellers, including to ones most people would find this a bit out of place in normal speech (though this could vary depending on the person)
- In every day speech, 屋 tends to be used for: food, small items, items with limited or specific uses, artisnal crafts, raw materials
- 店 tends to be used for vendors of greater variety, and more processed/artificial goods.
- To provide an example of the nuance difference, this writer suggests that a vendor of coffee beans feels more natural using 屋, whereas a sit-down cafe might take 店. (Indeed, this checks out based on my time in Japan. Specialty food shop? ○○屋. Sit-down eatery? 店.)
- Again, this is all just nuance and common use; no hard and fast rules.
Though not mentioned specifically here (I think it’s just taken as a given), I also think @Leebo’s comment above also holds weight, and is probably more relevant for your particular usage question. Then again, that goes for both ○○屋 and ○○店 (○○ is usually what they’re selling), which isn’t that dissimilar form English if you think about saying a “___store.” Though as in English, it’s not a hard rule. And I do feel that if either violate it, 店 is the more natural one to do it with.