The Latin name Gaul originally referred to the people of modern northern Italy and southeastern France, and gradually came to apply to a much larger area as the Romans expanded their control.

The Latin name Germania was how Caesar referred to the tribes that attacked across the Rhine.

The French say "Allemagne", which derives from the Allemani, a tribe that lived in modern Alsace. It's not exactly modern Germany, but it's kind of in that direction from France.

In English, the term Germany didn't so much survive as it was brought back from the Latin. The first use of "German" wasn't until after 1500, and Shakespeare used "Almain" interchangeably with "German".

There is a frequent occurrence in place naming where a culture applies the name of a nearby place to many more regions beyond it. Cis/Trans-alpine Gallia of 2nd Cent BCE was used in naming the eventual Ceasar's three parts of "Omnes Omnis Gallia". Asia used to be a province on the Aegean, but the name got stuck onto everything else in that direction. Africa was also a single province. The Allemani were taken as a representative of Germany from the viewpoint of what is now France. Canada originally meant some towns built along the Saint Lawrence river but came to mean a much larger place. The Indus river gave the name to a country that does not presently contain it.

It's kind of hard to come up with a reason why a particular name wins over another. Names so easily attach themselves onto other places that it's really not a matter of accuracy or correctness, but just a matter of shifting usage.

As you seem to be aware, you are asking several different questions here, some of which are hard to answer. It is not unusual to have a country go by different names in different languages, but why that may be the case can be difficult to ascertain. I will just try to answer the question of when the word "Deutschland" first appears.

According to the Deutsches Wörterbuch of the Brothers Grimm, the word first appeared in the 12th and 13th century, but rarely. It started appearing more frequently in the 16th century, where it is "often understood to include the German people," which I assume means as opposed to including other Germanic-language speakers like the Dutch.

http://www.woerterbuchnetz.de/DWB?lemma=deutschland

And speaking of the Dutch, the word "Dutch" is cognate with "Deutsch," both coming from the Germanic word "þeod," meaning "people" or "nation." So you could look up the English word "Dutch" in an etymological dictionary to learn more about the word's history, including the word, "Deutschland":

late 14c., used first of Germans generally, after c.1600 of Hollanders, from Middle Dutch duutsch, from Old High German duit-isc, corresponding to Old English þeodisc "belonging to the people," used especially of the common language of Germanic people, from þeod "people, race, nation," from Proto-Germanic *theudo "popular, national" (see Teutonic), from PIE root *teuta- "people" (cognates: Old Irish tuoth "people," Old Lithuanian tauta "people," Old Prussian tauto "country," Oscan touto "community").

As a language name, first recorded as Latin theodice, 786 C.E. in correspondence between Charlemagne's court and the Pope, in reference to a synodical conference in Mercia; thus it refers to Old English. First reference to the German language (as opposed to a Germanic one) is two years later. The sense was extended from the language to the people who spoke it (in German, Diutisklant, ancestor of Deutschland, was in use by 13c.).

http://www.etymonline.com/index.php?allowed_in_frame=0&search=dutch&searchmode=none

In addition to the other answers, it is important to take into consideration the tribal migrations of the end of the Western Empire. While the tribes collectively known as the Gauls originally inhabited France, this situation changed when the Franks migrated into Belgium and after the Romans left, became the dominant power in the region. Eventually due to military and cultural prowess, the ruling Franks became the most powerful culture and people in the region. As such the larger area became Frankish, displacing the previous identity for the inhabitants (who may or may not have been physically displaced at the same time).

However, the tribes across the Rhine didn't have this experience (apart from a short-lived union with the Franks under Charlemagne) and were more often known collectively as Germans. While small regions had their own names based on the prevailing tribal identity, no one tribe or identity became preeminent over the wider region. Therefore the collective identity became more dominant in the wider region than any one individual identity. For a time they attempted to call themselves East Franks, but this didn't last for long, barely more than a century between 840-962. The majority of the East Franks were too distinct, and hadn't had enough time under the supremacy of a dominant Frankish culture to consider themselves as Frankish as those in the heartlands. So the earlier collective identity of Germany reemerged in the 10th century.

English is very weird about what it calls countries/peoples. Sometimes we use the native name, other times we use the Latin name (or a Latinized name, occasionally a result of misunderstanding/mispronunciaton).

If you look at the native languages, you'll find a different story. France ceased to be called Gaul because of the rule of the Franks, which continued for quite some time; the last Capetian king died in the 14th century, and even the later French kings had Capetian ancestry.

For comparison, look at the names of those countries in a few of the relevant languages:

Latin:

Gallia, but in Medieval Latin, Francia or Francogallia.

Germania

French:

France

Allemagne

German:

Frankreich

Deutschland

So, as you can see, in their native languages, they now use German-derived terms for both countries.

As a vague point of interest, the first foreign peoples to come to Ireland were the Gauls and to this day, the Gaeilc word for foreigner is 'gall' (pronounced Gaul)

Germany have a vareity of names, not jsut germany. The germans call themself call their country deutschland. Whilst swedes call it Tyskland and finns call it Saxen after the province of saxony in northen germany. The name Francia derives from a germanic tribe named francs. Whoms decendants have keept controll of morden day france since the time of charlemange and even before.