Название города Салоники – существительное pluralia tantum (т. е. имеющее формы только множественного числа). Во множественном числе род не определяется.
Женскую (и мужскую) фамилию Ворона следует склонять.
Да, родительный падеж - города Московского.
Отдельного слова, которое бы называло самца кукушки, в современном русском языке нет.
В именительном падеже единственного числа возможны варианты: страз (мужской род) и страза (женский род). Поэтому в родительном падеже множественного числа допустимо: (много) стразов и страз.
См. в учебнике Е. И. Литневской в разделе Глагол главу Род. Число.