Корректно: газета «Поли́тико».

Правила таковы. Неизменяемое приложение, передаваемое цифрами, присоединяется дефисом: Чемпионат-2008. Но если цифре предшествует компонент, содержащий пробел, то вместо дефиса употребляется знак тире (с пробелами): Золотая осень – 2007.

См.: Правила русской орфографии и пунктуации. Полный академический справочник. М., 2006. – С. 163.

Правило звучит следующим образом: «В названиях праздников с начальной цифрой с прописной буквы пишется название месяца, например: 1 Мая, 8 Марта» (Правила русской орфографии и пунктуации. Полный академический справочник / Под ред. В. В. Лопатина. М., 2006).

Из этого правила следует, что написание любого праздника по образцу 8 Марта, 1 Мая является правильным. Однако устойчиво пишутся с прописной буквы названия месяцев только в названиях этих праздников.

Интересна история кодификации (закрепления в словарях и правилах) подобных названий.

В «Правилах русской орфографии и пунктуации» 1956 г. – своего рода орфографической конституции – указывалось: «Пишется с прописной буквы первое слово в названиях революционных  праздников и знаменательных дат, например: Первое мая, Международный женский день, Новый год, Девятое января (выделено нами. – Грамота.ру). Если начальное порядковое числительное в таком сложном названии написано цифрой, то с пpoписной буквы пишется следующее за ним слово, например: 9 Января, 1 Мая».

Однако Д. Э. Розенталь, который во второй половине ХХ в. расширял, уточнял и даже несколько изменял правила, со временем меняет рекомендации и относительно написания праздников. В «Справочнике по правописанию и литературной правке» 1967 г. из правила устраняются слова о революционном характере праздников: 

«С прописной буквы обычно пишется первое слово и собственные имена в названиях праздников, народных движений, знаменательных дат, например: Первое мая (1 Мая), Международный женский день, День Конституции, День Советской Армии,  День Победы, День авиации, День артиллерии, День печати, День шахтера... Девятое января (9 Января), Народный фронт, Новый год».

В справочниках Д. Э. Розенталя, изданных в конце 1990–2000-х гг. под редакцией других специалистов, была сделана попытка расширить список примеров на это правило и упоминаются государственные праздники 7 Ноября и 12 Июня.

Однако такие написания не закрепились. Видимо, эти даты не воспринимаются как названия праздников (в отличие от традиционных 8 Марта и 1 Мая).

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

В бессоюзном сложном предложении при обозначении пояснения, причины, обоснования, изъяснения допустимо употребление тире вместо двоеточия (особенно в художественной литературе и в публицистике). Вот, в частности, примеры из произведений К. Паустовского: Изредка в небе светилось голубоватое пятно — за тучками пробивалась луна, но тотчас гасла; Подснежники, наверное, уже прорастали в земле — их слабый травянистый запах просачивался сквозь снег; Слой облаков был очень тонок — сквозь него просвечивало солнце; На молу погасили огни — теплоход ушел; Татьяна Андреевна вздрагивала от сырости — после теплой каюты на палубе было свежо; Паханов крепко держал капитана за локоть — капитан был еще слаб после ранения; Ей хотелось заплакать — лом даже через варежки леденил руки; В армию меня тоже не берут — сердце заштопанное; Однажды зимой вышел я и слышу — стонет кто-то за оградой.  (Правила русской орфографии и пунктуации. Полный академический справочник / под ред. В. В. Лопатина. М., 2006. § 129.)

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

Вот примечание к правилу об однородных членах с обобщающим словом.

Допустимо используемое в современной практике печати при всех позициях обобщающих слов употребление тире, в том числе — перед перечислением (на месте традиционного двоеточия): Хороших байдарочников было всего трое — Игорь, Шуляев, Коля Корякин и, разумеется, сам Андрей Михайлович (Тендр.); Если бы его что-то выделяло среди других — талант, ум, красота... Но ничего такого у Дюка действительно не было (Ток.); Всё, всё услышал я — и трав вечерних пенье, и речь воды, и камня мертвый крик (Забол.); Я имел случай и счастье знать многих старших поэтов, живших в Москве, — Брюсова, Андрея Белого, Ходасевича, Вячеслава Иванова, Балтрушайтиса (Б. Паст.). (Правила русской орфографии и пунктуации. Полный академический справочник / под ред. В. В. Лопатина. М., 2006. § 36.)

1. «Правила русской орфографии и пунктуации» 1956 года – это официально действующие в настоящее время правила русского правописания. Официально действующие – но в ряде случаев значительно отстающие от современной практики письма, противоречащие ей, – такой вот парадокс. Написание с прописной буквы слова Бог не соответствует этим правилам, но в той же степени не соответствует им, например, написание с прописной слова Республика в сочетании Французская Республика, ибо согласно правилам 1956 г. слово республика пишется с прописной только «в официальных названиях советских республик и стран народной демократии». Раздел «Прописные буквы» в этом своде правил – пожалуй, наиболее устаревшая часть. В современных словарях и справочниках (некоторые из них приведены в пункте 2) рекомендации свода 1956 года пересмотрены, правила употребления прописных букв сформулированы заново, сейчас следует руководствоваться именно этими правилами.

2. См.: Правила русской орфографии и пунктуации. Полный академический справочник / Под ред. В. В. Лопатина. М., 2007; В. В. Лопатин, И. В. Нечаева, Л. К. Чельцова. Прописная или строчная? Орфографический словарь. М., 2007;  Мильчин А. Э., Чельцова Л. К. Справочник издателя и автора. М., 2003.

3. В политеистических религиях, действительно, существуют тысячи богов, поэтому, если речь идет об одном из верховных существ в политеистических религиях,  бог – нарицательное существительное (и пишется со строчной). Однако монотеистические религии основаны как раз на том принципе, что существует только один бог, поэтому в значении 'единое верховное существо в монотеистических религиях' слово Бог сближается с именем собственным, на этом и основана рекомендация писать это слово с прописной.

4. См. пункт 2. В этих изданиях употребляется именно слово «рекомендуется» (поэтому и мы так пишем). По поводу того, как оценивается написание бог / Бог в школьных сочинениях и диктантах, ничего не можем сказать (не знаем); вероятно, правильнее всего было бы не считать ошибкой ни то, ни другое написание, но рассказать ученикам о данной орфографической проблеме, о том, как она решается сейчас, какие рекомендации приведены в современных справочниках по правописанию.

В русском языке имя Ежи не склоняется. Правило таково: не склоняются мужские и женские имена и фамилии, оканчивающиеся на гласный -и.