Yes. Trolls and Night Elves are related through Dark Trolls - a subrace separate from Jungle Trolls (which is what the Darkspear are). They have many similarities, including some eye colors and their ears.
The thing you seem to be confused about is that Azshara actually wasn't the first Night Elf ruler. They "learned the language of the Titans" from Elune (as stated in Chronicle vol 1), which included words like "Kalimdor" and "Kaldorei" from that, and then built their empire. They made their capital, Elun'dris ("Eye of Elune"), and mastered sorcery. In the height of their magically-enhanced empire, Azshara became the queen. The capital was renamed Zin-Azshari in her honor. She couldn't have been the first queen, because the capital was already named, and the empire existed
before she was born.
Chronicle lists these events in order, with approximate dates. I'll list some of them for you.
-Troll-Aqir War: ~16,000 years ago (Troll subraces existed during this war - Amani defeated the Aqir, Dark Trolls claimed Well afterward)
-Mogu Empire: ~15,000 years ago (Thunder King: ~15,000-12,200 years ago)
-Kaldorei Empire: ~15,000-10,000 years ago (Azshara was born and ruled sometime during this period)
-Zandalari Invasion of Pandaria: ~11,900 years ago (Zandalari ruler was named
Zulathra)
-War of the Ancients & Sundering: ~10,000 years ago (Azshara became a Naga)
-Rastakhan's Reign: ~200 years ago until now (Not listed in Chronicle, mentioned on Wowpedia)
Azshara couldn't have had any relation to Rastakhan, and she was not born as a troll.