Why can't 'convenience store' be 'convenience shop'? And why can't 'coffee shop' be 'coffee store'? Can you tell me the exact difference between the two words?
When referring in general to outlets on the high street, "shop" is more common in British English, "store" more common in US English. A 'grocery store' in the US is usually called a 'grocers' in the UK, and we tend to say "I'm going to the shop", rather than "to the store". There are some exceptions - a 'general store' in British English is a type of shop that sells an array of goods, like a very small supermarket, although this term is quite outdated and not used much nowadays.
When it comes to "coffee shop", that seems to be an exception. I guess that a "store" is literally somewhere that stores (to keep amounts of stock in storage) things for sale. As coffee shops make fresh coffee on demand they don't really store the things they sell. A 'coffee store' sounds more like a place where you can buy coffee grounds to make coffee at home than a place you can buy a fresh cup of coffee.
Having said that, "store" has become more commonly used beyond US English since the introduction of online shopping. British online shoppers are used to terminology like "web store" and "shopping cart" (in real supermarkets, British English speakers call carts 'trolleys').
In American English, at least in my experience, shop implies a small place, usually run by a single person and focused on a particular kind of specialty product or service.
By contrast, a store is usually a larger establishment that carries a wide variety of products and is more focused on selling items than providing services.
So for example, I might go down to the repair shop to get an appliance fixed, but "repair store" doesn't make sense; that would make me think of a warehouse where they carry repair parts or something.
Similarly, if you said you were going to a "coffee store", I wouldn't imagine a café or Starbucks, but rather a store with big bins of coffee beans from many places that you can buy in bulk, or something of that nature. But that said, while "coffee shop" fits the general pattern, but it's actually a special case where that term is a set phrase, so it may act a little differently than the standard usage.