Вы совершенно правы. Двоеточие ставится в заголовках, распадающихся на две части с четким интонационным делением, отличающиеся смысловой насыщенностью, предельной краткостью, нередко и эмоциональной выразительностью. Первая часть называет общую проблему, место действия, лицо, а вторая — содержит конкретизацию названного в первой части: Экономическая реформа: опыт, проблемы, трудности; Разоружение: концепция, проблемы, механизм; Россия — Западная Европа: выгоды и перспективы сотрудничества; Звёздный рейс: работа на отлично!; Новый герой: поиски и находки; Женщина: семья и работа и т. п. 

Ответить на Ваш вопрос мы попросили проф. М. Я. Дымарского.

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

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

Мы не выполняем домашние задания. Вы можете воспользоваться словарями, размещенными на нашем портале. 

В словосочетании «На Берлин» предлог на употреблен в одном из своих обычных значений: "Употр. при указании на предмет, место, реже явление или человека, в сторону к-рых направлено движение, действие, к-рые являются ориентиром движения, распространения чего-л. Син. по направлению к. Идти несов. (бежать несов., ехать несов., плыть несов., лететь несов., спешить зд. несов., броситься, держать несов. курс …) на восток (юг, стук, свет, звук, крик, шум, меня …); дорога на Москву … 

Свойственные разговорной речи конструкции типа "поставки на Европу", "самолет на Японию" и т. п., очевидно, связаны с попытками говорящих проявить, подчеркнуть именно это значение: поставки, ориентированные на Европу; самолет, летящий по направлению к Японии. 

Верен второй вариант: 71 рейс.

Нам не удалось найти примера употребления, но как термин рекомендуем писать это слово через дефис.

Верно: будет пара недель. Слово пара должно стоять в форме именительного падежа.

Верно: бежать за самолетом (каким?), совершающим рейс.

На наш взгляд, в предложенных заголовках предпочтительнее поставить точку.

Д. Э. Розенталь рекомендовал ставить двоеточие в газетных заголовках, распадающихся на две части с четким интонационным делением, отличающиеся смысловой насыщенностью, предельной краткостью, нередко и эмоциональной выразительностью. Первая часть называет общую проблему, место действия, лицо, а вторая – содержит конкретизацию названного в первой части:

Экономическая реформа: опыт, проблемы, трудности;

Разоружение: концепция, проблемы, механизм;

Россия — Западная Европа: выгоды и перспективы сотрудничества;

Звёздный рейс: работа на отлично!

Корректно.