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

Правило гласит:

"Слитно пишутся сложные слова с первой иноязычной (интернациональной) частью, кончающейся на гласную. Перечень основных таких частей сложных слов:

• с конечным о: авто-, агро-, астро-, аудио-, аэро-, баро-, бензо-, био-, вело-, вибро-, видео-, гекто-, гелио-, гео-, гетеро-, гидро-, гомо-, дендро-, зоо-, изо-, кило-, кино-, космо-, макро-, метео-, микро-, моно-, мото-, невро-, нейро-, нео-, орто-, палео-, пиро-, пневмо-, порно-, психо-, радио-, ретро-, сейсмо-, социо-, спектро-, стерео-, термо-, турбо-, фито-, фоно-, фото-, эвако-, экзо-, эко-, электро-, эндо-, энерго-;
• с конечными а, е, и: авиа-, дека-, мега-, медиа-, тетра-; теле-; деци-, милли-, поли-, санти-;
• с двумя и более такими частями: аэрофотосъёмка, гидрогеохимический, метеорадиозонд, радиотелеуправление, спектрогелиограмма, фотокиносъёмочный, электрорадиооборудование; автомотовелогонки, астроспектрофотометрия, палеофитогеографический.

Однако вполне можно представить себе ситуацию, когда речь идет не о гонках, в которых участвуют три вида транспорта, а о перечислении гонок разного типа. Тогда уместно использовать висячий дефис: авто-, вело- и мотогонки.

Большой толковый словарь

Ко всему прочему -  вводное выражение, то же, что «кроме всего прочего, наконец». Выделяется знаками препинания, обычно запятыми.

Людям было неудобно, жарко, ко всему прочему, самого старого, совершенно седого генерала с планкой четырех орденов Красного Знамени и знаком «Почетный чекист» на габардиновом кителе в душновато-спертом, пахнувшем сеном воздухе стодолы сразу же охватило астматическое удушье. В. Богомолов, Момент истины.

В функции членов предложения эти слова не требуют постановки знаков препинания.

Вообще не сообразишь, за каким краем света находишься: ясно только, что вверх ногами ко всему прочему человечеству. М. Веллер, Ножик Сережи Довлатова. Но женщина бывает сострадательна, нежна, честна, справедлива только с тем, кого любит, и безжалостна ко всему прочему. И. Гончаров, Обрыв.

Слова «ко всему прочему» в значении «кроме всего» выделяются знаками препинания непоследовательно, ср.: Но еще ко всему прочему знаете что я подумал перед самым мгновением этим?.. Ю. Герман, Дорогой мой человек.

Да, такое существительное может быть написано слитно с не- в соответствии с правилом: «Слитно пишется не с именами существительными, обозначающими лиц и выражающими качественный оттенок; такие существительные в сочетании с приставкой не- приобретают значение противопоставления: специалисты и неспециалисты, профессионалы и непрофессионалы, футболисты и нефутболисты, филологи и нефилологи. Например: Все непрофессионалы, нефилологи, могут об этом и не знать; Фирма приглашает специалистов и неспециалистов для работы в сфере обслуживания».

Например: Но Брюсов, этот мужчина в поэзии par excellence, этот любитель пола вне человеческого, этот нелюбитель душ, этот: правое — левое, черное — белое, мужчина — женщина, на такие деления и эффекты, естественно, льстился [М. И. Цветаева. Герой труда (Записи о Валерии Брюсове) (1925)]; Недаром же французы сложили песенку, в которой загадочно, но вполне убедительно оценивают разницу между любителями и нелюбителями путешествий [В. А. Каверин. Верлиока (1981)] и др.

Слово памятник управляет дательным падежом: памятник В. И. Ленину. Но если слово памятник само стоит в дательном падеже, то вместо второго дательного употребляется родительный падеж: пропуск к памятнику (дат. п.) В. И. Ленина. См. «Словарь трудностей».

Город Тельмана – единственный город в Ленинградской области, название которого имеет форму родительного падежа. Подобные названия не рекомендуется употреблять без родового слова (ср.: в переулке Ильича, на удице Ленина), однако при таком употреблении они остаются несклоняемыми 

Сочетание разных возрастов ошибочным не является, употреблялось оно и раньше. Вот примеры из художественной литературы: На широкой поляне, окруженной древними дубами и непроходимым ломом, стояло несколько земляных куреней; а между ними на опрокинутых пнях, на вывороченных корнях, на кучах сена и сухих листьев лежало и сидело множество людей разных возрастов, в разных одеждах. А. Толстой, Князь Серебряный (1842–1862). Здесь же, у калитки, на утренней прогулке, семиклассники дожидались проезда ежедневного дилижанса, в котором, вдоль, слева и справа, сидели премиленькие девочки разных возрастов и в разных костюмах. А. Куприн, Юнкера (1932). Все мы, кондукторы, люди разных возрастов, характеров и взглядов, больше всего боялись, чтобы какая-нибудь из этих женщин не нашла при нас родного искалеченного человека. К. Паустовский, Повесть о жизни. Беспокойная юность (1954). Под водительством Касьянки подружки ее, девчонки разных возрастов и калибров, обливают водой длинный тесовый стол, поставленный на три опоры. В. Астафьев, Царь-рыба (1974).

У Ивана Алексеевича Бунина так:

Вот капля, как шляпка гвоздя,
Упала – и, сотнями игол
Затоны прудов бороздя,
Сверкающий ливень запрыгал –
И сад зашумел от дождя.

В принципе, на месте обоих тире могли бы быть поставлены запятые (но автор предпочел тире как более сильный знак).