1. Место героям найдется, были бы герои.

2. Буденновец - и житель города, и соратник Буденного. А вот буденовка - только головной убор. Жительница Буденновска - будеННовка.

Правило подходит и для этого случая: на земле Шацкой.

Правильно: Город воинской славы.

Да, по-русски тоже следует писать Костанай, именно такой вариант фиксируют сейчас словари собственных имен.

Действительно, это новая калька, словари такое значение не фиксируют. Метрополией корректно называть государство по отношению к своим колониям, но не город как центр чего-либо.

В произношении топонимов наиболее важной является традиция, а не собственно языковая логика. 

Запятыми выделено обстоятельство. Для смыслового выделения или для попутного пояснения могут обособляться обстоятельства, выраженные существительными в формах косвенных падежей (обычно с предлогами), особенно если при этих существительных имеются пояснительные слова: С приближением неприятеля к Москве, взгляд москвичей на своё положение не только не сделался серьёзнее, но, напротив, ещё легкомысленнее (Л. Т.) — смысловая нагрузка обособленного оборота в начале предложения усиливается в связи с тем, что к временному значению добавляется уступительное (взгляд москвичей становился легкомысленнее не только тогда, когда неприятель приближался к Москве, но и вопреки тому, что он приближался); Петя, после полученного им решительного отказа, ушёл в свою комнату и там, запершись от всех, горько плакал (Л. Т.) — совмещены два значения обособленного оборота — временное и причинное (ушел и горько плакал не только после того, как получил отказ, но и потому, что получил его). 

Действительно, в "Справочнике издателя и автора" А. Э. Мильчина, Л. К. Чельцовой дана рекомендация употреблять сокращение г. (и полное слово город) ограниченно, преимущественно перед названиями городов, совпадающими с фамилиями людей, например г. Пушкин, г. Королев.

Однако на практике (в канцелярской речи) сокращение г. и полное слово город употребляются перед названиями всех городов, в т. ч. с формантами -бург, -град и -город, напр.: г. Волгоград, г. Санкт-Петербург, город Шлиссельбург, город Калининград.

Для смыслового выделения или для попутного пояснения могут обособляться обстоятельства, выраженные существительными в формах косвенных падежей (обычно с предлогами), особенно если при этих существительных имеются пояснительные слова: С приближением неприятеля к Москве, взгляд москвичей на своё положение не только не сделался серьёзнее, но, напротив, ещё легкомысленнее (Л. Т.) — смысловая нагрузка обособленного оборота в начале предложения усиливается в связи с тем, что к временному значению добавляется уступительное (взгляд москвичей становился легкомысленнее не только тогда, когда неприятель приближался к Москве, но и вопреки тому, что он приближался); Петя, после полученного им решительного отказа, ушёл в свою комнату и там, запершись от всех, горько плакал (Л. Т.) — совмещены два значения обособленного оборота — временное и причинное (ушел и горько плакал не только после того, как получил отказ, но и потому, что получил его). В приведенных выше примерах возможность обособления ставится в зависимость от степени распространенности оборота, его близости к основной части предложения, наличия добавочных оттенков значения, места по отношению к сказуемому, стилистической задачи и т. д., поэтому обособление факультативно.