Saying "Je vais au restaurant/cinéma" is actually pretty different from "Je vais au restaurant/cinéma français" (which doesn't meant what you want by the way, see at the bottom).
The marché is a little different, I'll cover that later.
When you say "Je vais au restaurant/cinéma", it's a general statement about the idea of going to somewhere, while the other is about going to a specific place. It's easier to see the difference with cinéma :
I'm going to the movies
I'm going to a French movie theater
express different ideas. In French, the general statement will go with "au" (au restaurant, au cinéma), the specific one will go with "à un/dans un". "à un" is less correct but you might still encounter it.
Je vais dans un/(à un) restaurant/cinéma français
Je suis dans un/(à un) restaurant/cinéma français
About the marché, I said it was different, and it's because usually, there's only one. Even in big cities, you'll be referring to the closest one. It's like saying "I'm going to the city hall", it's clear which one you're talking about, so you say "the marketplace" not "a marketplace".
However, it's more rare but if you really need to say "a marketplace" you can, and it will behave the same.
"Je vais au restaurant Français" wouldn't mean "I'm going to a French restaurant" but :
"I'm going to the French restaurant", which implies you've already mentioned it. That's just a un vs le situation.
"Je vais au cinéma Français" would technically be correct, if you were in a non-French city and there was one French cinema among other local cinemas (it's the same for restaurants by the way). That's not what you would say if you're in France and go to a random cinema.
It also sounds weird for a French speaker because "cinéma Français" is a well-known word to designate the French cinema industry.