1a. I entered a coffee shop
i) trying to have a cup of coffee
ii) trying to drink a cup of coffee,
Problem: trying to. It means you were trying to have/drink a cup of coffee as you entered the shop. That is, you had a cup of coffee in your hand and were you trying to drink it.
Solution:For example,
wanting a cup of coffee / in need of a cup of coffee 1b. but I was told that they could not serve me because there wasn't any coffee left at that moment. Suggestion: at the time; at that moment means, at that very moment in time, so why not reduce it to something a tad more efficient? 2. I went out of the coffee shop and turned the corner because, straight ahead, there was a restaurant I used to
i) know

ii) go
to
Note, if you visited the coffee shop around the corner only once or twice or so before, then
knew would be a better verb than
used to know or used to go to because
used to means a past routine, habit.
3. I had previously been there when I visited the city.
=> Work on 2. first.
4. I was served with a hot cup of coffee, there. Problem: people are served with summons, and food is served with side orders.
Served with <a drink or meal> is English, but not as common as
served <a drink or meal>.
Solution: served a hot cup of coffee 5.The wind was blowing hard outside, so I decided to spend some time in that warm atmosphere.
i)
outside 
.
ii)
the wind was blowing strongly
Note,
blowing hard is a collocation, and it works just as well as
blowing strongly. Neither sounds formal. (By the way, adverbs are slowly losing -
ly, so you'll also hear and read
blowing strong.)