Поскольку это не географическое название конкретного места, нужно писать с маленькой буквы: ехали по обским степям.
Правилен первый вариант.
Нормативно: полька. Вариант полячка – устаревший.
Женскую (и мужскую) фамилию Ворона следует склонять.
Это слово по родам не изменяется.
Верно: Ново-Тихвинский.