Citation: 5A_558/2016 E. 8

Vu ce qui précède, le recours est admis, l'arrêt annulé et la cause renvoyée au Juge unique de la Cour civile II du Tribunal cantonal du canton du Valais pour instruction et nouvelle décision dans le sens des considérants. Conformément à l'art. 26 al. 2 CLaH80, il n'est pas perçu de frais judiciaires devant le Tribunal fédéral. Vu le sort du litige, l'intimée, qui a succombé dans ses déterminations devant le Tribunal fédéral, versera au recourant une indemnité de dépens pour la procédure fédérale (art. 68 al. 1 et 2 LTF). La Caisse du Tribunal fédéral versera par ailleurs une indemnité à la curatrice de l'enfant pour ses honoraires de représentation. Par ces motifs, le Tribunal fédéral prononce :