European monarchies are extremely intertwined, all European dynasties are related to each other, it's not surprising that they use very similar symbols. For example, take a look at the family tree of the German monarchs:

Looking at that royal mess, and considering the hereditary nature of heraldry, I think it's quite obvious how we ended up with only two main symbols of European monarchy, the lion and the eagle. That said, and while the choice of the eagle is easily explained, the lion is a bit more enigmatic and I don't think we can do much more than speculate.
The use of lions might have been widespread in the House of Normandy, and the first known use of the lion in coat of arms in a hereditary fashion comes from one of the dynasty's members, Henry I of England. When Geoffrey V, Count of Anjou was knighted in 1127, according to Wikipedia:
He [Henry] placed to hang around his neck a shield painted with golden lions
When Geoffrey V died in 1151 an enamel effigy showing three lions was placed on his tomb. A very similar effigy was placed on the tomb of Geoffrey's grandson, William Longespée.

It's quite possible that Henry I also used the lion as his symbol, and by passing it on to his son-in-law Geoffrey unwittingly created the tradition of hereditary coat of arms. Henry II of England, Geoffrey's son, also adopted the lion, and according to Wikipedia:
He was probably the first king of England to use a heraldic design: a signet ring with either a leopard or a lion engraved on it. The design would be altered in later generations to form the royal seal of England.
His son, Richard I of England (Richard the Lionheart) formally adopted the three lions from his grandfather's shield as the Royal Arms of England. Political alliances (this was after all the time of the Crusades), intermarriages, and conquests all played a part in the symbol, in one form or another, finding its way to most European coats of arms.
Still, the question remains: Why a lion? It can be speculated that it's an early Christian symbol (see: Daniel in the lions' den), or just a widespread symbol of bravery, as it has been used in similar fashions by several civilizations, some decisively non Christian and with little contact with the Christian world at the time (for example the Han Dynasty's guardian lions). The legendary Hercules could also be the source of the using the lion as a symbol of bravery, his first labour being slaying the Nemean Lion (and then fashionably wearing its skin as a hat ;)
Lastly, a fascinating opinion is that the lion became widely associated with knighthood and chivalry in the 1170s because of the popularity of Chrétien de Troyes' romance Yvain, the Knight of the Lion, that influenced later works of Arthurian legend all around Europe, like Iwein and Owain, or the Lady of the Fountain.