Ciao, tralasciando javascript/ajax quindi tutto in php e con ricaricamento pagina dopo selezione NAZIONE, e' abbastanza selezionare la nazione, sull'onchange della select(almeno questo con javascript) esegui il submit del form e passi il value della select alla pagina. Con questo fai una query per estrarre tutte le regioni che come campo nazione(o identificativo di quella) avranno quella selezionata. Torni quindi alla pagina con la nazione gia selezionata e la seconda select con tutte le regioni estratte.
Volendo puoi non visualizzare la seconda select fino a che non e' stata selezionata la nazione.

Calcola poi che se vengono compilati altri campi e poi viene selezionata la nazione, la pagina ricarica e perdi gli altri dati( fai quindi i vari controlli per recuperare tutti i dati gia inseriti)