Well maybe there appearance is not entirely fit for an Elezen but did you know that Louisoix actually turned into Phoenix with the power of the Twelve after he defeated Bahamut. I am rather convinced that Garuda and Ramuh were at one point Elezen I do find it unlikely that Bahamut, Odin, Good King Moogle Mog, or even Titan was Elezen but they had to have been mortal beings whom were given power from the twelve and probably turned into Primals by an even greater power like Zodiark and then summoned by those who like remembered them for some great all mighty deed and hence their prayers brought those Primals into the mortal realm in the form that they had taken when they called upon the Twelve to grant them power that is by all means the best explanation for how they came to be.