As to your question regarding why a lion is considered the symbol of Orlais, particularly when the lion is a creature native only to eastern Thedas, the answer is quite simple. It adorns the crest of the Valmonts, the family that has ruled the empire since the end of the Exalted Age, and in truth it is the Valmonts which have come to represent Orlais. Before them, the Orlesian symbol was that of the descendants of Kordillus Drakon: a dragon.
As to why the lion adorns their crest? That dates back to the time of Lambert Valmont, a young captain of Orlais who distinguished himself at the Battle of Ayesleigh, that great and infamous battle that ended the Fourth Blight. It is said that young Valmont disregarded orders during the battle, taking his forces to relieve the beleaguered Antivans and saving them from absolute destruction. Though his superiors were at first chagrined, chalking up the captain's actions to an infatuation with a certain Antivan camp follower (this, incidentally, has never been confirmed), it later came to light that the Antivan force had been led by King Azar Adalberto Campana himself. In the political realignment following the Blight's end, Antiva was an important ally to Orlais—and Lambert Valmont was an Antivan hero. He was given the hand of one of King Azar's daughters in marriage and elevated to noble rank, with a valiant lion to adorn his newly created heraldry. The Orlesian emperor was forced to respond in kind, granting Valmont a marquisate. Imagine, if you will, the hero returning to Val Royeaux from the Blight, sporting a wife with royal blood and the honors of two nations. This is why jealous nobles called him the Swaggering Lion, a nickname he embraced.
It was Lambert Valmont's son, Alphonse, who later led the civil war against the usurper, Xavier Drakon. He killed Xavier in single combat, giving rise to the great Orlesian legend of the Lion Slaying the Dragon, putting an end to the Drakon dynasty as he assumed the throne... and changing the Orlesian symbol forever.