Unless the word has a clearly defined gender, you usually use the article of the German translation.
e.g. the star -- means "der Stern" in German
so if you use it like:
superstar --> der Superstar
Also, in German in a compound-noun, such as Superstar, the article is always defined by the LAST partial word, which is star in this case.
die Mütze ==> die Donaudampfschifffahrtskapitänsmütze
Champs Elysées is a particular bad example, because it's a compound noun that is not really written together, not in German either.
So you'd first have to define if you use the article assigned to Champs (das Feld), or Elysée (article = ? ), depending on whether you consider it a compound noun or not...
I'd make a little longer sentence for that it becomes clear:
"Wir gingen auf der "Champs Elysées"-Strasse spazieren".
compound-noun consisting of "Champs Elysées" and (die) Strasse as last component.
so it becomes clear:
die "Champs Elysée(s)"
Since the position of the word in your sentence is the "Dativ-Objekt (Wem)", it's:
Wir gingen auf der Champs Elysées spazieren.
(Wir gingen auf der Strasse spazieren).
If it was a German word, you'd definitely omit the ending "s", but since this is a French name (Eigenname), it's better to leave the "s".
As to "le Front National".
Der Verein "Front National" --> der Front National
you could also use
Die Partei "Front National" --> die Front National
but "die" sounds a bit odd, probably because of the pronounciation of "Front", which rather requires "der" in German (Sprachgefühl).
it's a bit arbitrary, as always with the article, there is no real rule, only statistics.
The usual article used in the newspapers are "der Front National", or you could just translate it to "Die Nationale Front", but nobody ever does this.
About the "la Gare de St. Lazare":
der Bahnhof von St. Lazare
==> der Garde de St. Lazare.
here, the rule of the article of the translated word applies.
If you have problems determining the article of a Eigenname, if possible I suggest you use a proper noun and make the Eigenname a "attribute" of that noun, like
die Partei "Front National", that way the article is clearly determined by the noun, and you circumvent the problem relatively elegantly.
To everything else than a Eigenname, the rule of the article of the translated word applies.