Well, to be honest, Air makes a ton of sense. Aaracockra fly, love freedom and open spaces, etc. It would be downright weird if they didn’t have an affinity for Air. However I like thinking outside the box sometimes… I am sure the aaracokra would approve…
Sun- They feel the sun on their backs all the time. Arguably more often, and more closely than other race. Mystical help with dealing with it would be needed.
Silt- There is an important element that needs to be considered. It’s canonically confirmed that there are Aaracokra who live in or near the Silt Sea. Silt in the air can weigh down wings and block visibility. Of course there would be a demand for a cleric of Silt.
Rain- Water is rare and precious on Athas. Rain even more so. For an aaracokra, just flying through Rain would be a ecstatic and mystical experience. Yeah, in practical terms you don’t want to fly in the rain, but imagine how it would feel…
Those are the Paraelemental options. Let’s turn to some crazy options.
Lalali Puy- The Oba of Gulg. The sorcerer queen. The Scourge of the Aaracokra in the Cleansing Wars. Why on the brown sands of Athas would the Aaracokra worship her? Why do people sacrifice people to the Dragon? FEAR. People sometimes forget that polytheistic cultures often have deity that is feared or reviled. You would pray to them to avert their wrath. To appease them. Could that have happened here?
Daskinor - Another sorcerer king? Why him? This is the flip side of Lalali Puy. It doesn’t need to be a SK. What I am suggesting is that the aaracokra may have mistaken some other super powerful entity as a savior or shield from Lalali Puy. Something like this actually happened in Japan to a ninja clan. A clan got attacked, and they fled to another shogun… who was friends with the other. Guess who pledged themselves to whom?
Magma - This is the crazy one. Why Magma? FOOLISH CHILD. YOU HAVE NOT LIVED UNTIL YOU HAVE RISEN ON THE UPDRAFT FROM A VOLCANO!
Also, Nazca lines. They should be totally into that.