For the MC’s nickname, maybe Red? Because of her red hair?
For the MC’s last name, I thought of a few:
Swallow (like the bird)
Fern
Beschel
Attal
Surnames for Alexander:
Norman
Henchten
Haymell
I’m not sure if the surnames fit the first names at all to be honest. 