Оба варианта возможны. Сочетание в этой связи просторечным не является (см. его фиксацию в словарях: Правильность русской речи / Под ред. С. И. Ожегова. М., 1965, с. 184; Трудности словоупотребления и варианты норм русского литературного языка / Под ред. К. С. Горбачевича. Л., 1974, с. 401; Большой толковый словарь / Под ред. С. А. Кузнецова. СПб., 1999, с. 1164). Соответствуя норме современного русского литературного языка, это устойчивое cочетание употребляется как наречие со значением 'связывая со сказанным выше' и служит своеобразной формулой перехода от одной мысли к другой.

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

Вот что написано о подобных ошибочных конструкциях в справочнике Ю. А. Бельчикова «Практическая стилистика современного русского языка» (М., 2012):

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

В современном русском языке такие конструкции не соответствуют норме.

Существует следующее орфографическое правило: 

 При выборе написания о  или а  в безударных глагольных корнях не следует использовать для проверки глаголы несовершенного вида с суффиксом −ыва (−ива). Например, для проверки безударной гласной в корнях глаголов броса́ть, топта́ть, смотре́ть, молча́ть следует привлекать такие слова и формы, как бро́сить, перебро́ска, разбро́с, то́пчет, смо́трит, смо́тр, мо́лча, умо́лкнуть, но не глаголы типа набрасывать, вытаптывать, рассматривать, умалчивать, для которых характерно чередование гласных о – а (ср. зарабо́тать – зараба́тывать, усво́ить – усва́ивать и т. п.).

Предложенные вами варианты корректны и соответствуют нормам русского языка. Однако перевод названий — это не столько перевод, сколько транскреация, то есть воссоздание текста на новом языке для новой аудитории. Вспомним удачный перевод названия фильма Die Hard как «Крепкий орешек». 
Представляется, что переводчик сам может сделать выбор: либо использовать предложенные варианты, либо не переводить вовсе. При этом переводить Охотник х Охотник не вполне корректно, так как для русского языка такая конструкция не характерна. 
Насколько нам известно, в среде поклонников этого аниме его называют по-английски, не используя перевод, то есть это будет привычным и понятным названием.

Правило гласит: " При выборе написания о или а в безударных глагольных корнях не следует использовать для проверки глаголы несовершенного вида с суффиксом −ыва (−ива). Например, для проверки безударной гласной в корнях глаголов броса́ть, топта́ть, смотре́ть, молча́ть следует привлекать такие слова и формы, как бро́сить, перебро́ска, разбро́с, то́пчет, смо́трит, смо́тр, мо́лча, умо́лкнуть, но не глаголы типа набрасывать, вытаптывать, рассматривать, умалчивать, для которых характерно чередование гласных о – а (ср. зарабо́тать – зараба́тывать, усво́ить – усва́ивать и т. п.)".

Не только в официальном названии Бельгии употребляется форма родительного падежа (Королевство Бельгии), то же самое – в официальных названиях Нидерландов и Великобритании (Королевство Нидерландов; Соединенное Королевство Великобритании и Северной Ирландии). Хотя большая часть названий королевств – в именительном падеже: Королевство Норвегия, Королевство Швеция, Королевство Испания и др.

Почему Бельгия и Нидерланды выбиваются из этого ряда, вопрос интересный. Возможно, это связано с традицией употребления, наименованием в языке-источнике, а может быть, и с федеративным устройством этих государств: обычно названия, в которых присутствует форма родительного падежа, характерны для федеративных государств, ср.: Соединенные Штаты Америки, Соединенное Королевство Великобритании и Северной Ирландии (Бельгия – тоже федерация, состоящая из двух сильно отличающихся друг от друга регионов – Фландрии и Валлонии).

В слове Африка корень африк-, совпадающий с основой слова.

Явления, сопровождающие образование слов афроамериканец и Евразия, содержат признаки как словосложения (образование сложных слов), так и аббревиации (образование сложносокращенных слов). В этих словах в качестве первого компонента используются сокращенные корни афр- (сокращение корня африк-) и евр- (сокращение корня европ-), что сближает эти слова со сложносокращенными, ср.: матчасть (мат- ― сокращенный корень матери[j]-), запчасти (зап- ― сокращенный корень запас-) и т. п. С другой стороны, в слове афроамериканец выделяется соединительная гласная о, а использование соединительных гласных (интерфиксов) характерно для словосложения, ср: пароход. В слове Евразия отсутствует материально выраженный соединительный элемент, однако его можно считать нулевым, ср.: Новгород.

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

Номинативные предложения могут быть нераспространенными (Тишина. Мороз.) и распространенными. Просьба освободить вагоны – распространенное номинативное предложение, в котором инфинитив освободить выступает в роли несогласованного определения: просьба (какая?) освободить. Употребление в роли определения весьма характерно для инфинитива, ср.: желание (какое?) любить, аналогично наука побеждать, радость творить, мужество остаться.