Везде требуется тире: Папуа — Новая Гвинея, Кривой Рог — Сортировочный, Северный Рейн — Вестфалия» и Мекленбург — Передняя Померания.

Да, вторая часть названия склоняется. Правильно: достопримечательности Папуа – Новой Гвинеи.

Следует писать через тире с пробелами: Папуа – Новая Гвинея (если написать через дефис, получится сложное слово Папуа-Новая, т. е. будут нарушены смысловые отношения между единицами). Написание через тире Папуа – Новая Гвинея  зафиксировано нормативными словарями русского языка, в том числе «Русским орфографическим словарем» Российской академии наук.

Под освоенностью в данном случае понимается то, что название является привычным для носителя языка вследствие более или менее частого употребления в устной и письменной речи; четких критериев (дата заимствования, количество словоупотреблений и др.) нет.  Например, такие названия, как Вевак, Наматанай, Маданг (Папуа – Новая Гвинея), вряд ли известны большому числу носителей языка, поэтому при употреблении с родовым словом город их целесообразно не склонять. А такие названия, как Казань  и Уренгой, давно употребляются в русском языке, они известны (или, по крайней мере, должны быть известны) большинству говорящих и пишущих по-русски, поэтому их можно назвать освоенными русским языком.

Что касается названия нашей планеты, то оно не склоняется при употреблении с родовым словом. Правильно: на Земле, но: на планете Земля.