В названиях улиц, площадей, переулков, проспектов и пр. с большой буквы пишутся все слова, кроме родовых терминов (т. е. самих слов улица, площадь, проспект и т. п.), служебных слов, а также слов года, лет. Правильно: ул. Уральского Полка, ул. Треугольник Депо, ул. Свердловский Тракт.

Название корректно согласовывать с родовым словом, при этом для инверсии (на площади Юбилейной) должны быть веские причины. Предпочтительно: на Юбилейной площади (ср. на Красной площади). Вариант на площади Юбилейная бюрократически-канцелярский и не соответствующий литературной норме.

В названиях улиц, площадей, проспектов и т. п. с прописной буквы пишутся все слова, кроме родовых терминов (т. е. самих слов улица, проспект, площадь  и т. п.) и слов года, лет. Что касается названий микрорайнов и пр., здесь действует такое правило: в составных географических названиях с прописной буквы пишутся слова, которые употребляются не в своем обычном значении. Правильно: улица Теплый Ключ, микрорайон Теплый Ключ (т. к. это не ключ, а район).

В названиях улиц, площадей, переулков, проспектов и пр. с большой буквы пишутся все слова, кроме родовых терминов (т. е. самих слов улица, площадь, проспект и т. п.), служебных слов, а также слов года, лет. Поэтому слово североморцев тоже надо писать с большой буквы. Корректно написание через дефис (приложение присоединяется дефисом): проспект Героев-Североморцев. Ср.: улица Героев-Панфиловцев (в Москве; такое написание зафиксировано орфографическим словарем В. В. Лопатина, И. В. Нечаевой, Л. К. Чельцовой «Прописная или строчная?»).

Такие слова не склоняются.

Да, это корректный вариант оформления предложения.

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

Слово улица лишнее. Улица – это улица, а проезд – это проезд. Правильно: Большой проезд, Цветной бульвар, Лиговский проспект и т. п.