Robrenn: This is of course the ideal place for Celtic style Fairies.
Eusdria: Germanic/Norse fairies would fit well here.
Bellayne: I could see English style fairies here. Would they all have cat features though?
Renardy: With the French influence you could also draw on Gaul/Celtic myths like with Robrenn. As with Bellayne, perhaps dog features on the fairies?
Savage Baronies: I don't know enough about Spanish or South American fairy tales. The first thing that comes to mind is
Herath: Not sure about this realm. Wood Imps might be found here, given their affinity for spiders?

Tortle lands: Not sure. Turtle like Pooka?
Wallara: I don't know if there is an official take on the relationship between fairies and Spirits. I like the idea of Fey being similar to Spirits, but more mischievious in nature, while some Spirits are more harmonious and others warped and evil.
Oltec Ruins: I am wondering if the Fey from the Azca HWR could still be hanging out in some of these ruined lands.
City States: These lands were settled by people of Traldar origins. Did they bring with them slavic style fairies? Perhaps Hags, Crones etc?
What are your ideas for Spirits and Fairies on the Savage Coast?
See also my map of Mystara's Fairy Plane
-Havard