Что, если пара, состоящая в однополом браке решит переехать, и соответственно получить гражданство в стране, где эти самые браки запрещены?

Брак будет считаться недействительным. А дальше все зависит от того, куда именно переехали и какие законы относительно однополых отношений действуют в стране по отношению к легальности гомосексуальных пар. В Йемене, например, или Судане казнить могут, где-то просто уголовно преследовать могут, а где-то просто не регистрируют браки, никак не относясь на законодательном уровне к парам.