Faits :
A.
A.A._ (1982) et B.A._ (1983), tous deux de nationalité roumaine, se sont mariés le 9 septembre 2007. De leur union est issue une fille, C.A._, née en 2008.
La famille a d'abord vécu en Roumanie, puis les époux A._ sont venus s'installer en Suisse au mois d'octobre 2012. L'enfant est demeurée chez sa grand-mère paternelle en Roumanie, jusqu'à l'automne 2013, où elle a rejoint ses parents en Suisse.
Les époux A._ ont suspendu définitivement la vie commune le 17 octobre 2013. Le père est retourné seul en Roumanie.
A.a. Par ordonnance de mesures superprovisionnelles du 22 novembre 2013, le Président du Tribunal d'arrondissement de la Broye et du Nord vaudois, saisi par la mère, a attribué la garde de l'enfant commun à la mère et suspendu le droit aux relations personnelles entre l'enfant et le père.
A.b. A la fin de l'année 2013, la mère a introduit action en divorce en Roumanie. Par jugement du 30 janvier 2014, exécutoire dès son prononcé, le Tribunal civil de Y._ (RO) a ratifié l'accord de médiation survenu le 17 décembre 2013 et, partant, a prononcé le divorce des époux A._, maintenu l'autorité parentale conjointe des père et mère, attribué la garde de l'enfant au père, sous réserve d'un droit de visite de la mère, et fixé le lieu de résidence de l'enfant auprès du père.
A.c. Le 20 décembre 2013, la fille des parties a été confiée à son père en Roumanie. L'enfant est demeurée vivre auprès de son père et la mère a exercé son droit de visite à deux ou trois reprises. La fille a fréquenté l'école maternelle de Y._ (RO) jusqu'au 1 er avril 2015. En 2014 et début 2015, le père a cependant séjourné en Suisse. Durant l'absence du père de Roumanie, le Tribunal civil de Y._ (RO) a "délégué" l'autorité parentale sur l'enfant à la grand-mère paternelle. Lorsque le père a regagné la Roumanie, il a à nouveau vécu avec sa fille, auprès de sa mère.
A.d. Par ordonnance de mesures protectrices de l'union conjugale du 10 février 2014, le Président du Tribunal d'arrondissement de la Broye et du Nord vaudois a confié la garde de l'enfant à la mère et institué un droit de visite surveillé du père.
La mère a sollicité la reconnaissance de ce prononcé auprès des autorités roumaines. Statuant le 3 mars 2015, la Cour d'appel de Z._ (RO) a rejeté la demande, considérant que la cause avait déjà été jugée par le tribunal roumain, dont le jugement exécutoire l'emportait sur le prononcé postérieur de l'autorité suisse.
A.e. Par ordonnance pénale du 24 avril 2014, le Ministère public de l'arrondissement de La Côte a reconnu le père coupable de voies de fait qualifiées, d'injure et de menaces qualifiées à l'endroit de son ex-épouse.
A.f. Le 15 octobre 2014, la mère a introduit une action en modification du jugement de divorce en Roumanie, tendant à obtenir l'autorité parentale et le transfert, chez elle, du lieu de résidence de la fille.
A.g. Le 17 avril 2015, le père a subi, lors d'une agression, un traumatisme crânien, des contusions cérébrales, ainsi qu'une hémorragie sous-anachnoïdienne. Lors de son admission à l'hôpital, il était en état d'ébriété avancé, était agité et présentait des " phénomènes de sevrage (alcool + drogues) ". Il est demeuré hospitalisé jusqu'au 21 avril 2015.
A.h. Le 28 avril 2015, le père a déclaré, par écrit, qu'il consentait à ce que sa fille " voyage en Suisse, accompagnée de sa mère ", spécifiant que ce document " lui était nécessaire à la Police des frontières, afin de sortir du pays, ainsi que partout où il sera nécessaire ". L'autorisation était délivrée pour une année, du 28 avril 2015 au 28 avril 2016. Ce titre a été établi et légalisé en l'étude d'un notaire de Y._ (RO), lequel a certifié que le père avait compris le contenu de sa déclaration et qu'elle représentait sa volonté.
Par déclaration notariée du 12 août 2015, le père a révoqué l'autorisation précitée du 28 avril 2015.
A.i. Au mois d'avril 2015, l'enfant est revenue en Suisse avec sa mère. Dès le mois d'août 2015, elle a été scolarisée à l'école primaire de U._ (VS), en Suisse.
A.j. Le 14 août 2015, le père a déposé une requête en retour de l'enfant auprès de l'autorité centrale roumaine.
Le 29 février 2016, le Ministère de la justice de Roumaine a signifié à l'Office fédéral de la justice de la Confédération suisse la " demande de restitution " de l'enfant présentée par le père.
A.k. Par arrêt du 3 mars 2016, le Tribunal civil de Y._ a, après avoir procédé à l'audition de témoins et sollicité un rapport de l'autorité de protection de l'enfant, attribué l'autorité parentale et la garde de la fille des parties à la mère, mettant en évidence les antécédents judiciaires du père, sa consommation fréquente d'alcool et de stupéfiants, sa prédisposition au scandale, et sa violence verbale et physique manifestée à l'encontre de son ex-femme. Le tribunal roumain a également exposé que, à la suite du traumatisme crânien subi en avril 2015, le père n'était plus à même de prendre soin de sa fille, que la révocation de l'autorisation du 28 avril 2015, peu de temps après l'avoir consentie, constituait un comportement inconséquent, qu'il était incapable de prendre les décisions de nature à servir le bien de l'enfant et qu'il bénéficiait de l'aide de ses parents.
B.
Le 21 avril 2016, A.A._ a adressé une requête en retour de l'enfant mineur au Tribunal cantonal du canton du Valais et sollicité le prononcé de mesures provisoires immédiates.
B.a. Le 25 avril 2016, le Juge unique de la Cour civile II du Tribunal cantonal du canton du Valais a fait interdiction à la mère de quitter le territoire du Valais avec l'enfant des parties ou de faire déplacer celle-ci en dehors du territoire du canton du Valais, jusqu'à droit connu sur le sort de la requête en retour de l'enfant.
L'enfant a été entendue par sa curatrice au mois de mai 2016, sans donner l'impression d'avoir été instrumentalisée, et déclaré qu'elle souhaitait demeurer auprès de sa mère, qu'elle était certes attachée à son père et à sa grand-mère paternelle, mais qu'elle craignait que son père la ramène en Roumanie.
Le 6 juin 2016, le père a versé à la cause la déclaration d'appel qu'il avait déposée le 26 mai 2016 contre le jugement du 3 mars 2016 du Tribunal civil de Y._.
B.b. Statuant par décision du 14 juillet 2016, le Juge unique de la Cour civile II du Tribunal cantonal du canton du Valais a rejeté la requête en retour de l'enfant.
C.
Par acte du 27 juillet 2016, A.A._ interjette un recours en matière civile au Tribunal fédéral. Il conclut à l'annulation du jugement querellé et à sa réforme en ce sens que le retour de l'enfant C.A._ en Roumanie est ordonné, aux frais de la mère, le cas échéant, avec le concours de la force publique. Il requiert en outre la gratuité de la procédure fédérale, une indemnité de dépens à la charge du Tribunal fédéral et le remboursement de ses frais (voyage, représentation, recherche de l'enfant), par la mère.
D.
Invitées à se déterminer sur le recours, l'intimée, de même que la curatrice de l'enfant, ont conclu toutes deux au rejet du recours, sous réserve toutefois de l'admission de la conclusion tendant à ce qu'il ne soit pas perçu de frais de procédure. Quant au juge cantonal, il a déclaré se référer aux considérants de son arrêt.

Considérant en droit :
1.
La décision statuant sur la requête en retour d'un enfant à la suite d'un déplacement international d'enfant est une décision finale (<ref-law>) prise en application de normes de droit public dans une matière connexe au droit civil, singulièrement en matière d'entraide administrative entre les États contractants pour la mise en oeuvre du droit civil étranger (art. 72 al. 2 let. b ch. 1 LTF; <ref-ruling> consid. 1.2; <ref-ruling> consid. 2b; arrêts 5A_429/2015 du 22 juin 2015 consid. 1; 5A_584/2014 du 3 septembre 2014 consid. 1.1; 5A_880/2013 du 16 janvier 2014 consid. 1). Le Juge unique de la Cour civile II du Tribunal cantonal du canton du Valais a statué en instance cantonale unique conformément à l'art. 7 al. 1 de la loi fédérale sur l'enlèvement international d'enfants et les Conventions de La Haye sur la protection des enfants et des adultes du 21 décembre 2007 (LF-EEA, RS 211.222.32); il y a ainsi exception légale au principe du double degré de juridictions cantonales (<ref-law>; arrêts 5A_584/2014 du 3 septembre 2014 consid. 1; 5A_799/2013 du 2 décembre 2013 consid. 1 et 5A_822/2013 du 28 novembre 2013 consid. 1.1). Le recours a en outre été interjeté dans la forme (<ref-law>) et le délai de dix jours (art. 100 al. 2 let. c LTF) prévus par la loi, par une partie ayant pris part à la procédure devant l'autorité précédente et justifiant d'un intérêt digne de protection à la modification ou à l'annulation de la décision attaquée (<ref-law>), de sorte que le recours en matière civile est en principe recevable.
2.
Le recours en matière civile peut être formé pour violation du droit fédéral et du droit international (art. 95 let. a et b LTF). Le Tribunal fédéral applique le droit d'office (<ref-law>), sans être lié ni par les motifs de l'autorité précédente, ni par les moyens des parties; il peut donc admettre le recours en se fondant sur d'autres arguments que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 3; <ref-ruling> consid. 1.4). Cela étant, eu égard à l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, il n'examine en principe que les griefs soulevés (<ref-ruling> consid. 2; <ref-ruling> consid. 1.3; <ref-ruling> consid. 1.4). Le recourant doit par conséquent discuter les motifs de la décision entreprise et indiquer précisément en quoi il estime que l'autorité précédente a méconnu le droit (<ref-ruling> consid. 2 et les références). De surcroît, le Tribunal fédéral ne connaît de la violation de droits fondamentaux que si un tel grief a été invoqué et motivé à cet égard par le recourant ("principe d'allégation", <ref-law>; <ref-ruling> consid. 2.2; <ref-ruling> consid. 3.3; <ref-ruling> consid. 1.2, 397 consid. 1.4 in fine), c'est-à-dire s'ils ont été expressément soulevés et exposés de façon claire et détaillée (ATF <ref-ruling> consid. 1.2; <ref-ruling> consid. 1.4.2; arrêt 5A_223/2016 du 28 juillet 2016 consid. 2.1).
3.
Le recours a pour objet le retour immédiat de l'enfant mineure C.A._ en Roumanie auprès de son père, au regard des dispositions de la Convention de La Haye du 25 octobre 1980 sur les aspects civils de l'enlèvement international d'enfants (CLaH80, RS 0.211.230.02).
3.1. La CLaH80 a pour but d'assurer le retour immédiat des enfants déplacés ou retenus illicitement dans tout État contractant et de faire respecter de manière effective dans les autres États contractants les droits de garde et de visite existants dans un autre État contractant (art. 1 er CLaH80). A teneur de l'art. 4 de la CLaH80, la Convention s'applique à tout enfant qui avait sa résidence habituelle dans un État contractant immédiatement avant l'atteinte aux droits de garde ou de visite (art. 5 CLaH80). Le retour de l'enfant dans son pays de provenance ne peut être ordonné que si le déplacement est illicite au sens de l'art. 3 CLaH80 et si aucune des exceptions au retour prévues par l'art. 13 CLaH80 n'est réalisée, en d'autres termes, uniquement dans les cas prévus par la convention.
3.2. Dans l'arrêt déféré, le juge cantonal retient que " la résidence habituelle de C.A._ était à Y._, au domicile de son père lorsque sa mère l'a déplacée au mois d'avril 2015", alors que le père était seul titulaire du droit de garde. L'autorité précédente a ensuite retenu que, par déclaration écrite du 28 avril 2015, le père avait consenti à un déplacement temporaire de l'enfant - indiquant la durée du 28 avril 2015 au 28 avril 2016 -, qu'il n'avait certes pas donné son accord à une modification du lieu de résidence, mais n'avait pas pour autant spécifié que l'autorisation ne portait que sur l'exercice du droit de visite, ni fixé une date de retour. Le juge cantonal a exposé qu'une fois donné, le consentement ne pouvait pas être rétracté. Il en a conclu que l'autorisation de séjourner en Suisse durant un an n'avait pas cessé de déployer ses effets, partant, que le refus de la demande de retour était justifié en vertu de l'art. 13 al. 1 let. a CLaH80, pour ce motif déjà.
Pour le surplus, le magistrat cantonal a relevé que l'arrêt en modification du jugement de divorce du 3 mars 2016 du Tribunal civil de Y._ attribuant à la mère l'autorité parentale sur l'enfant et déplaçant le lieu de résidence habituelle de la fille au domicile de sa mère, avait été entrepris par le père, en sorte que ce jugement ne pouvait pas valoir acquiescement postérieur au déplacement, mais qu'il convenait néanmoins d'éviter d'exposer l'enfant à un double retour en cas de rejet de l'appel par les juges roumains. Le juge cantonal a enfin rappelé que la demande en retour avait été introduite une semaine avant l'écoulement du délai d'un an de l'art. 12 CLaH80, en sorte qu'à quelques jours près, il lui aurait appartenu de déterminer si l'enfant s'était intégré à son nouveau milieu, mais que cette question pouvait néanmoins souffrir de rester indécise.
3.3. En l'espèce, la cour de céans constate que tant la Suisse que la Roumanie ont toutes deux ratifié la CLaH80 (art. 1 er CLaH80) et que l'enfant mineure C.A._ se trouvait en Roumanie immédiatement avant le déplacement en Suisse, auprès de son père, titulaire du droit de garde (art. 4 et 5 CLaH80), selon le jugement du 30 janvier 2014 du Tribunal civil de Y._ ( cf. supra consid. 3.2). Il s'ensuit que les dispositions de la CLaH80 sont applicables au cas d'espèce.
4.
Le recourant s'en prend d'abord à l'établissement des faits par le juge cantonal, exposant qu'il s'est fondé sur des faits constatés arbitrairement ou que les constatations de fait sont manifestement incomplètes (art. 9 Cst.).
Le père entend faire corriger l'état de fait en relation avec le déroulement de la médiation effectuée en Roumanie dans le cadre du jugement de divorce, estimant que l'état de fait tel qu'il est actuellement rédigé - il précise que la mère "ignorait, en outre, que le médiateur était un ami de son mari" - jette le discrédit sur sa personne, alors que le médiateur était en réalité un ami de l'avocat du père. Le recourant soutient aussi que le contenu de l'autorisation notariée du 28 avril 2015 n'a pas été reproduit de manière exhaustive, menant à une interprétation erronée de la volonté exprimée dans ce document, alors que le consentement ou l'acquiescement au déplacement de l'enfant est une question de fait. A cet égard, il relève que le texte clair et exhaustif du document indique qu'il a donné son consentement à ce que sa fille voyage en avion, de Roumanie en Suisse, accompagnée de sa mère, aux fins d'exercer le droit de visite, mais qu'il n'a nullement consenti à un transfert de la garde ou au déplacement du lieu de résidence. Le recourant affirme en outre que la révocation de cette autorisation de voyage a eu lieu le 11 juin 2015 déjà et non le 12 août 2015 comme cela ressort de manière erronée de l'état de fait du juge cantonal.
Le père estime aussi que l'état de fait est incomplet sur trois points. En premier lieu, le père dénonce l'absence de mention que la durée de l'autorisation de voyager du 28 avril 2015, jusqu'au 28 avril 2016, est identique à la date de validité du passeport de sa fille. Deuxièmement, l'état de fait ne retranscrirait arbitrairement pas les déclarations de la mère à teneur desquelles elle a exposé que "lorsque j'ai pris ma fille pour m'établir avec elle en Suisse, je n'ai pas invité mon ex-mari à signer des documents portant sur le transfert de garde". Ces allégations seraient pourtant cruciales car elles attesteraient du fait que la mère savait que le recourant n'avait pas consenti au déplacement du lieu de résidence de leur fille. L'arrêt querellé serait aussi lacunaire sur les constatations et l'examen de la question d'un éventuel acquiescement de sa part au non-retour de l'enfant en Roumanie.
4.1. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). En tant que cour suprême, il est instance de révision du droit et non pas juge du fait. Il ne peut donc rectifier ou compléter les faits, partant s'en écarter, que si ceux-ci ont été établis de façon manifestement inexacte - soit de manière arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 2; <ref-ruling> consid. 4.2; <ref-ruling> consid. 1.5; <ref-ruling> consid. 1.4.1) - ou en violation du droit au sens de l'<ref-law> (<ref-law>) et si la correction du vice est susceptible d'influer sur le sort de la cause (art. 97 al. 1 in fine LTF). Le recourant qui soutient que les faits ont été établis d'une manière manifestement inexacte doit soulever ce grief en présentant une argumentation claire et détaillée ("principe d'allégation, <ref-law>, cf. supra consid. 2).
4.2.
4.2.1. S'agissant de la médiation intervenue dans le cadre du divorce des parents en Roumanie, cet élément de fait, qui constate ce qu'a compris la mère, ne contient en conséquence aucun jugement de valeur; il n'a manifestement aucune incidence sur l'application de la CLaH80 au cas d'espèce, partant sur le sort de la présente cause ( cf. supra consid. 4.1). De surcroît, une action en modification du jugement de divorce est actuellement pendante en Roumanie, dont l'audience d'appel se tiendra le 14 octobre prochain selon les allégations du recourant lui-même, de sorte que le jugement de divorce initial n'est en l'état pas pertinent pour examiner le droit de garde et l'attribution parentale de l'enfant C.A._; tel est a fortiori aussi le cas des circonstances dans lesquelles ce jugement est intervenu. Enfin, il sied de relever qu'il résulte uniquement de l'appréciation du recourant que ce constat jetterait le discrédit sur sa personne. Vu ce qui précède, cet élément est dénué de pertinence; partant, il n'y a pas lieu d'examiner si cette insertion factuelle est ou non conforme aux déclarations protocolées de l'intimée, et, le cas échéant, de corriger l'état de fait sur ce point ( cf. supra consid. 4.1).
4.2.2. En tant que le recourant se plaint d'un état de fait incomplet s'agissant de l'autorisation qu'il a rédigée le 28 avril 2015, son grief doit être admis. Le juge cantonal a manifestement reproduit uniquement certaines phrases de ce document, qu'il considérait comme essentielles. Or, cette autorisation constituerait, à teneur de l'arrêt déféré, la preuve du consentement du père à "un déplacement temporaire de l'enfant", sans "date de retour antérieure au 28 avril 2016". La correcte application du droit, singulièrement de l'art. 13 al. 1 let. a CLaH80 nécessite toutefois que le consentement du père, chez qui l'enfant était domiciliée, soit établi. Dans cette optique, la pièce attestant de la prétendue approbation du recourant au déplacement et au non-retour de sa fille revêt une importance particulière pour le sort de la présente cause, impliquant la prise en considération de l'intégralité du texte. Il s'ensuit que l'état de fait doit être complété, en ce sens que la pièce n° 9 est reproduite in extenso, à tout le moins s'agissant du contenu de la déclaration du père : "Le soussigné A.A._ [ n° passeport, adresse, identification et avertissement des sanctions d'un faux témoignage] déclare son consentement que sa fille mineure C.A._ [ n° passeport], née le 22.04.2008, dans la ville de Y._, département de Y._, voyage en SUISSE, par avion, sur la route Bucarest-Genève, entre 28.04.2015 et 28.04.2016, accompagnée par sa mère, Mme B.A._ [ n° passeport, adresse et identification]. La présente déclaration lui est nécessaire à la Police des frontières, afin de sortir du pays, ainsi que partout où il sera nécessaire".
4.2.3. Certes, il ressort de l'arrêt entrepris que "[p]ar déclaration notariée du 12 août 2015, A.A._ a révoqué l'autorisation donnée le 28 avril précédent", alors que le recourant allègue avoir révoqué son autorisation le 11 juin 2015 déjà; néanmoins, la modification de cette prétendue erreur n'est nullement susceptible d'influer sur le sort de la cause, le juge cantonal ayant retenu que "[u]ne fois le consentement donné, il ne pouvait être rétracté", de sorte que la date de la révocation de l'autorisation n'est pas un élément pertinent pour statuer sur la présente affaire. Dans ces circonstances, faute de pertinence, cette constatation n'est pas un élément essentiel de l'état de fait, en sorte qu'il n'y a pas lieu de le corriger à cet égard ( cf. supra consid. 4.1).
4.2.4. La correspondance de date, à savoir le 28 avril 2016, entre l'échéance de l'autorisation et la date d'échéance du passeport de l'enfant, ne figure en effet nul part dans l'arrêt déféré. Toutefois, l'on ne voit pas en quoi cet élément aurait une quelconque incidence sur l'interprétation de la portée de l'autorisation - dont le contenu est désormais reproduit dans son intégralité ( cf. supra consid. 4.2.2) -, singulièrement en quoi une date différente serait un indice de la volonté du père d'accepter une modification du lieu de résidence de l'enfant. Au demeurant, le recourant ne motive pas plus avant son grief, se limitant à qualifier cette constatation d' "indispensable pour déterminer [ses] allégations". Autant qu'il répond à l'exigence minimale de motivation (<ref-law>; cf. supra consid.2), le grief est mal fondé, la constatation n'ayant aucune influence pour l'issue de l'affaire ( cf. supra consid.4.1).
4.2.5. Il faut concéder au recourant que lors de l'audience du 17 mai 2016 devant le Juge unique de la Cour civile II du Tribunal cantonal valaisan, la mère a déclaré que "lorsque j'ai pris ma fille pour m'établir avec elle en Suisse, je n'ai pas invité mon ex-mari à signer des documents portant sur le transfert de garde", et que ces propos n'ont pas été retranscrits dans l'état de fait de la décision querellée. Prise isolément, cette déclaration peut sembler pertinente pour le sort de la cause. Toutefois, il convient de replacer cette phrase dans le contexte dans lequel elle a été prononcée, à savoir que la mère expliquait qu'elle avait versé 3'000 fr. au recourant lorsqu'elle a pris sa fille en Suisse, qu'elle n'a ni quittance pour ce versement, ni fait signer à celui-ci de documents sur le transfert de la garde. Il ressort donc de ces affirmations que la mère a toujours considéré être en droit de déplacer la résidence de leur fille en Suisse, position procédurale qu'elle a défendue depuis le dépôt de l'action en retour de l'enfant. Aussi, l'on ne voit pas en quoi la mention de ces déclarations dans l'état de fait serait en définitive propre à influer sur la cause, étant précisé que les conclusions en rejet de la requête de retour de l'enfant figurent dans l'exposé des faits de la décision du juge précédent ( cf. supra consid. 4.1). Partant, le grief est également rejeté sur ce point.
4.2.6. Enfin, s'agissant de la question d'un éventuel consentement au non-retour de la fille en Roumanie, la critique du recourant est d'emblée irrecevable (<ref-law>; cf. supra consid. 2). Se limitant à citer de la jurisprudence, à reprocher à l'autorité précédente de ne pas avoir procédé à un tel examen et à présenter sa propre appréciation juridique, le père n'énumère ainsi pas les éléments de faits qui auraient été rendus objectivement vraisemblables et qui n'auraient pas été relatés dans l'état de fait, alors qu'ils auraient permis l'examen d'un éventuel acquiescement postérieur au déplacement du lieu de résidence de l'enfant. Eût-elle été recevable, la critique aurait quoi qu'il en soit été dénuée de pertinence, dès lors que le juge cantonal, ayant admis l'existence d'un consentement au déplacement de l'enfant, pouvait s'épargner, dans ces conditions, l'examen d'un acquiescement postérieur au déplacement ou l'acceptation du non-retour de l'enfant.
5.
Le recourant expose que le Juge unique de la Cour civile II du Tribunal cantonal valaisan a violé l'art. 12 al. 1 CLaH80, en procédant à l'examen de l'intégration de la fille en Suisse et de intérêt de l'enfant à demeurer dans le pays dans lequel il a été déplacé, alors que le juge n'avait pas à effectuer cette appréciation prévue à l'art. 12 al. 2 CLaH80, dès lors que sa requête en retour de l'enfant a été déposée dans l'année suivant le non-retour litigieux et même le déplacement contesté. Le père fait valoir que, lorsque la demande en retour de l'enfant est déposée dans le délai d'un an fixé à l'art. 12 al. 1 CLaH80, cette norme prescrit le retour automatique de l'enfant, sans examen de l'adaptation de l'enfant dans le nouveau pays.
5.1. Il ressort de la décision entreprise que le juge cantonal a constaté que " la demande a été introduite une semaine avant l'écoulement du délai d'une année de l'article 12 al. 1 CLaH80 " et que "[ à] quelques jours près, il [ lui] aurait appartenu de déterminer si l'enfant s'était intégrée à son nouveau milieu. Le cas échéant, C.A._ n'aurait vraisemblablement pas pu être renvoyée". L'autorité précédente a souligné que "depuis plus d'une année ", l'enfant avait noué des liens culturels et sociaux en Suisse, et a estimé que le laps de temps de près d'un an avant de saisir le Tribunal cantonal d'une requête en retour de sa fille n'était pas insignifiant et que, même si les enfants en bas âge avaient une grande faculté d'adaptation, le déracinement de la fille de son nouveau milieu habituel durant la procédure d'appel en Roumanie était susceptible de provoquer chez elle un trouble dans son esprit, qu'il y avait lieu de prévenir. Le juge cantonal en a conclu que, pour ce motif déjà, la demande en retour devait être rejetée.
5.2. Lorsqu'un enfant a été déplacé ou retenu illicitement et qu'une période de moins d'un an s'est écoulée à partir du déplacement ou du non-retour au moment de l'introduction de la demande, l'autorité saisie ordonne son retour immédiat (art. 12 al. 1 CLaH80). Dans la systématique de la CLaH80, la question de l'intégration de l'enfant dans son nouveau milieu n'est pertinente que si l'autorité est saisie d'une requête en retour de l'enfant après l'expiration d'un délai d'un an depuis le déplacement illicite (art. 12 al. 2 CLaH80; arrêt 5A_617/2015 du 24 septembre 2015 consid. 3.3.1.3).
5.3. Nonobstant le constat que la requête en retour avait été déposée avant l'échéance de la période d'un an fixée par l'art. 12 CLaH80 - comptée à partir du déplacement de la fille déjà -, le juge précédent a estimé, de manière contradictoire, que l'intégration de l'enfant dans son nouveau milieu " depuis plus d'une année " justifiait que l'on évite un nouveau déracinement de la fille pour la durée de la procédure d'appel. En examinant les conséquences d'un retour de la fille en Roumanie pour son bien-être, en dépit du constat que le délai d'un an n'était pas échu, l'autorité précédente a appliqué par anticipation l'art. 12 al. 2 CLaH80 et fondé sa décision sur ce motif. Ce faisant, le Juge unique a violé l'art. 12 al. 1 CLaH80, qui impliquait le retour immédiat de la fille, sans examen de l'intégration de celle-ci en Suisse.
6.
Le recourant soutient que le juge cantonal a violé l'art. 13 al. 1 let. a CLaH80, exposant, d'une part, qu'il n'a pas consenti - singulièrement par sa déclaration du 28 avril 2015 auprès du notaire roumain - au déplacement et au non-retour de sa fille, et, d'autre part, que l'arrêt roumain en modification du jugement de divorce du 3 mars 2016 n'est pas définitif, partant, pas exécutoire, car il fait l'objet d'un appel qui sera jugé en séance le 14 octobre 2016, en sorte qu'en l'état il n'y a ni acquiescement postérieur, ni risque de double retour si le jugement roumain devait lui attribuer la garde de l'enfant.
6.1. En principe, lorsqu'un enfant a été déplacé ou retenu illicitement, l'autorité saisie ordonne son retour immédiat (art. 1 let. a, 3 et 12 al. 1 CLaH80), à moins que l'une des exceptions prévues à l'art. 13 CLaH80 ne soit réalisée (arrêts 5A_1003/2015 du 14 janvier 2016 consid. 5.1; 5A_705/2014 du 15 octobre 2014 consid. 3.1). Les exceptions au retour prévues à l'art. 13 CLaH80 doivent être interprétées de manière restrictive, le parent ravisseur ne devant tirer aucun avantage de son comportement illégal (arrêts 5A_479/2012 du 13 juillet 2012 consid. 5.1, publié in PJA 2012 p. 1630 et in SJ 2013 I p. 29; 5A_285/2007 du 16 août 2007 consid. 4.1, publié in PJA 2007 p. 1585).
6.2. Sous le grief de violation de l'art. 13 al. 1 let. a CLaH80, le recourant soutient premièrement que l'autorisation de voyager qu'il a rédigée le 28 avril 2015 ne constitue pas un consentement au déplacement de l'enfant, au sens de l'exception prévue à l'art. 13 al. 1 let. a CLaH80 et que la mère n'a pas démontré l'accord du père. Il expose avoir donné son accord à un déplacement temporaire et non pas à un changement de résidence de l'enfant, selon le texte de la déclaration du 28 avril 2015. Le père souligne aussi que, contrairement à ce qu'à retenu le juge cantonal, lorsqu'il a révoqué l'autorisation de voyage du 28 avril 2015, il n'a pas révoqué son consentement à l'établissement de sa fille en Suisse, dès lors qu'il ne l'avait jamais donné, mais a exprimé sans délai son refus de modifier le lieu de résidence habituel de l'enfant.
6.2.1. Il ressort de l'arrêt entrepris que le Juge unique de la Cour civile II du Tribunal cantonal valaisan a considéré que le père avait donné son accord à un déplacement temporaire de sa fille en Suisse, qu'il n'avait certes pas consenti à une modification du lieu de résidence, mais que celui-ci n'avait pas pour autant spécifié que l'autorisation ne portait que sur l'exercice du droit de visite et n'avait ainsi pas fixé de date de retour. L'autorité précédente a jugé que, vu le traumatisme crânien du père, cet élément nouveau avait imposé une réglementation différente de la garde de l'enfant, commandée par le bien de la fille : le père n'étant plus à même, provisoirement, de prendre soin de celle-ci, il a donné son accord à ce qu'elle séjourne avec sa mère et que, contrairement à ce que le père avait prétendu, il ne s'agissait donc pas d'un accord sur l'exercice du droit aux relations personnelles, mais d'un document devenu nécessaire par son impossibilité d'exercer la garde.
6.2.2. La première exception prévue à l'art. 13 al. 1 let. a CLaH80 prévoit que l'autorité judiciaire de l'État requis n'est pas tenue d'ordonner le retour de l'enfant lorsque le parent ravisseur qui s'oppose à ce retour établit que l'autre parent, qui avait le soin de l'enfant, avait consenti ou a acquiescé postérieurement à ce déplacement ou à ce non-retour. La CLaH80 ne prévoit pas de présomption relative à l'accord au non-retour de l'enfant, mais exige la preuve de ce consentement (art. 13 al. 1 CLaH80), laquelle doit répondre à des exigences particulièrement élevées (arrêts 5A_1003/2015 du 14 janvier 2016 consid. 5.1.1; 5A_705/2014 du 15 octobre 2014 consid. 3.1 et les nombreuses références citées; 5A_577/2014 et 5A_578/2014 du 21 août 2014 consid. 4.4; 5A_822/2013 du 28 novembre 2013 consid. 3.3); des déclarations conditionnelles ne suffisent pas (arrêts 5A_705/2014 du 15 octobre 2014 consid. 3.1; 5A_577/2014 et 5A_578/2014 du 21 août 2014 consid. 4.4; 5A_520/2010 du 31 août 2010 consid. 3). Le consentement, respectivement, l'acquiescement (exprès ou par actes concluants) du parent qui avait la garde dans le pays d'origine doit être exprimé clairement (arrêt 5A_705/2014 du 15 octobre 2014 consid. 3.1).
6.2.3. Selon le texte complet de l'autorisation du 28 avril 2015 - eu égard aux termes "voyage", "par avion, sur la route", "nécessaire à la Police des frontières, afin de sortir du pays" ( cf. supra consid. 4.2.2) -, il apparaît que ce document fait référence à un voyage, non à l'établissement de l'enfant ou à une modification du lieu de résidence, notamment faute de précision sur la durée du séjour projeté en Suisse ou de désignation d'un lieu de destination. Dès lors que le texte de l'autorisation n'est pas équivoque et a été rédigé par un notaire de manière claire, il n'y avait pas lieu de recourir à l'interprétation à laquelle le juge précédent a procédé au regard des circonstances, singulièrement des séquelles de l'agression du père ( cf. supra consid. 6.2.2). Il s'ensuit que la déclaration du 28 avril 2015 ne saurait être comprise comme une " autorisation de séjour durant une année ", ainsi que l'a retenu le juge cantonal, ni a fortiori comme le consentement du père à la modification du lieu de résidence de sa fille. Le grief de violation de l'art. 13 al. 1 let. a CLaH80 doit donc être admis sous cet angle.
6.2.4. En l'absence de consentement donné par le parent gardien de l'enfant avant le déplacement, le point de savoir si la révocation dudit consentement est licite ou non peut souffrir de demeurer indécis.
6.3. En second lieu, le recourant conteste qu'il existe un acquiescement postérieur au sens de l'art. 13 al. 1 let. a CLaH80 découlant de la décision rendue par la Roumanie, après le déplacement de sa fille. Il admet qu'un jugement a certes été rendu le 3 mars 2016 par le Tribunal civil de Y._ attribuant l'autorité parentale à la mère et déplaçant le lieu de résidence habituelle de l'enfant en Suisse, mais il soutient que ce jugement n'est pas constitutif d'un acquiescement, faute d'être entré en force et exécutoire. Il expose avoir formé appel contre ce jugement, lequel sera jugé en séance le 14 octobre 2016 à 9h30, en sorte que la décision rendue le 3 mars 2016 en faveur de la mère de l'enfant n'est pas exécutoire et ne peut donc avoir d'influence sur le prononcé ou le refus du retour de l'enfant. De surcroît, le recourant ajoute que la mère n'a ni allégué, ni a fortiori démontré, l'existence d'une décision provisoire pour la durée de la procédure d'appel, qui serait immédiatement exécutoire, selon laquelle la résidence de l'enfant serait fixée auprès d'elle en Suisse.
6.3.1. S'agissant de la décision roumaine, l'autorité précédente a rappelé que le Tribunal civil de Y._ avait attribué l'autorité parentale à la mère et déplacé le lieu de résidence habituelle de l'enfant du domicile de son père à celui de sa mère, que le père avait entrepris ce jugement et qu'on ignorait si l'arrêt sur appel devait être rendu à brève échéance. Le juge cantonal a ainsi retenu que le retour de l'enfant, dans l'intervalle, était de nature à l'exposer à un nouveau renvoi si l'appel devait être rejeté, partant, qu'il fallait prévenir le risque de double retour.
6.3.2. Lorsque l'État requérant rend, postérieurement au déplacement, une décision accordant la garde au parent ravisseur, il y a lieu d'admettre que le retour de l'enfant ne doit pas être ordonné, car une telle décision de l'autorité de l'État de provenance de l'enfant prive alors de pertinence une argumentation fondée sur le caractère illicite du déplacement contesté au sens de l'art. 13 al. 1 let. a CLaH80 (arrêts 5A_1003/2015 du 14 janvier 2016 consid. 5.1.1; 5A_584/2014 du 3 septembre 2014 consid. 6.2.1; 5A_884/2013 du 19 décembre 2013 consid. 4.2.2.2).
6.3.3. Contrairement à ce que soutient le recourant, le Juge unique de la Cour civile II du Tribunal cantonal valaisan n'a pas retenu que le jugement roumain attribuait, de manière définitive, l'autorité parentale à la mère et déplaçait par conséquent le lieu de résidence habituelle de l'enfant chez sa mère, partant, que ce jugement serait constitutif d'un acquiescement postérieur au sens de l'art. 13 al. 1 let. a CLaH80. L'autorité précédente a uniquement retenu que la date de l'arrêt sur appel était encore indéfinie, et que, au vu du contenu du jugement de première instance, le renvoi de la fille en Roumanie dans l'intervalle - sur la base de la CLaH80 - exposait l'enfant à un nouveau renvoi si cet appel devait être rejeté. Le juge cantonal n'a donc pas considéré que le jugement du 3 mars 2016 constituait ainsi un acquiescement postérieur, mais que la prévention du risque de double retour constituait, dans l'attente d'un arrêt définitif des autorités du pays de provenance sur ces questions, une exception au sens de l'art. 13 al. 1 let. a CLaH80. En l'occurrence, l'art. 13 al. 1 let. a CLaH80 n'a nullement trait à des questions d'opportunité, partant, ne consacre pas le risque d'un double retour comme exception, mais se limite à la prise en considération d'éléments factuels ( cf. supra consid. 6.3.2). Il s'ensuit qu'en admettant qu'il existait un risque de double retour induit par le jugement roumain du 3 mars 2016 dont est appel et que ce risque consacrait une forme d'acquiescement pour la durée de la procédure de deuxième instance, le juge cantonal a méconnu la portée de cette disposition. Seul l'arrêt sur appel qui interviendra le 14 octobre 2016, lorsque cette décision sera entrée en force et devenue exécutoire, sera constitutif d'un acquiescement postérieur au déplacement et non-retour illicites de la fille. La violation de l'art. 13 al. 1 let. a CLaH80 doit donc également être admise sous cet angle.
7.
Saisie d'une requête en retour de l'enfant, l'autorité judiciaire de l'État dans lequel l'enfant a été déplacé ou est retenu illicitement n'est pas compétente pour procéder à un examen approfondi de la situation complète afin de rendre une décision sur le fond de la cause statuant sur les questions d'autorité parentale et de garde de l'enfant. Dans le cadre du mécanisme de la CLaH80, il suffit que les juridictions nationales examinent et motivent succinctement les éléments plaidant en faveur du retour de l'enfant dans le pays de provenance, ainsi que les motifs invoqués d'exclusion au rapatriement de l'enfant, à la lumière de l'intérêt supérieur de l'enfant et en tenant compte des circonstances du cas d'espèce (arrêt 5A_584/2014 du 3 septembre 2014 consid. 6.2.3)
Vu ce qui précède, il appartient aux autorités suisses saisies du cas d'espèce d'examiner tous les éléments justifiant et excluant le retour de l'enfant dans le pays de provenance. Dès lors que le juge cantonal a admis que tant l'art. 12 al. 2 CLaH80 que l'exception de l'art. 13 al. 1 let. a CLaH80 constituaient des éléments justifiant le non-retour de la fille en Roumanie, il a laissé ouverte l'exception de l'art. 13 al. 2 CLaH80 ( cf. infr a consid. 7.1) et n'a pas examiné l'exception prévue à l'art. 13 al. 1 let. b CLaH80 ( cf. infr a consid. 7.2). Or, l'admission du recours s'agissant des griefs des art. 12 et 13 al. 1 let. a CLaH80 ( cf. supra consid. 5 et 6) a pour conséquence que la réalisation de l'un ou de l'autre de ces deux exceptions doit être examinée, question de droit dont le Tribunal fédéral se préoccupe d'office (<ref-law>; cf. supra consid. 2).
7.1.
7.1.1. Le juge précédent a exposé que la fille s'était opposée à son retour et manifesté sa volonté de demeurer auprès de sa mère. Le magistrat cantonal a cependant estimé que, en raison de son âge (8 ans), l'enfant n'était " très vraisemblablement pas à même de se forger une opinion personnelle à propos de la question spécifique du retour dans son pays d'origine ", en sorte que, au vu de l'issue de la requête en retour, la question de l'opposition de l'enfant pouvait souffrir de rester indécise.
7.1.2. L'art. 13 al. 2 CLaH80 dispose que l'autorité judiciaire de l'État requis peut aussi refuser d'ordonner le retour de l'enfant si elle constate que celui-ci s'oppose à son retour et qu'il a atteint un âge et une maturité où il se révèle approprié de tenir compte de cette opinion. Un enfant a atteint un degré de maturité suffisant au sens de cette disposition lorsqu'il est en mesure de comprendre le sens et la problématique de la décision portant sur le retour. Il doit en particulier être capable de saisir que la procédure ne concerne ni la question du droit de garde, ni celle de l'autorité parentale, mais tend uniquement à rétablir la situation antérieure au déplacement illicite; il doit aussi être conscient que le point de savoir dans quel État et auprès duquel de ses parents il vivra à l'avenir sera tranché, après son retour dans le pays d'origine, par les autorités judiciaires de ce pays (<ref-ruling> consid. 2.4). L'opposition de l'enfant constitue une exception au principe du retour en cas de déplacement illicite; elle ne confère pas à l'enfant le droit de choisir librement le lieu de séjour de la famille. L'opposition au sens de l'art. 13 al. 2 CLaH80 doit être qualifiée, c'est-à-dire être exprimée avec une certaine fermeté et reposer sur des motifs particuliers et compréhensibles (<ref-ruling> consid. 4; arrêts 5A_930/2014 du 23 décembre 2014 consid. 6.1.3; 5A_799/2013 consid. 5.7). Selon la jurisprudence, un enfant de 8 ans n'est, a priori, pas capable de se forger une opinion personnelle à propos de la question spécifique du retour dans son État d'origine pour la durée de la procédure tendant à l'attribution du droit de garde (<ref-ruling> consid. 2.4; arrêt 5A_930/2014 du 23 décembre 2014 consid. 6.3.2).
7.1.3. En l'occurrence, il ressort de l'arrêt déféré que le juge cantonal a constaté que la fille des parties était âgée de 8 ans et a indiqué qu'elle ne semblait pas suffisamment mature pour exprimer son opinion sur cette question spécifique. Faute d'élément propre au cas d'espèce permettant de considérer qu'exceptionnellement un enfant de 8 ans est capable d'exprimer son opposition qualifiée à son retour, le magistrat cantonal ne pouvait pas, eu égard à la jurisprudence précitée ( cf. supra consid. 7.1.2 in fine), laisser la question ouverte, partant, suggérer que l'opposition de l'enfant aurait pu être une exception supplémentaire au retour. Sur la base de ses constatations, le juge précédent ne pouvait que conclure que l'exception consacrée par l'art. 13 al. 2 CLaH80 n'était pas satisfaite.
7.2. La dernière exception au retour de l'enfant (art. 13 al. 1 let. b CLaH80) n'a pas été traitée dans la décision entreprise, le juge cantonal ayant déjà admis trois motifs plaidant contre le rapatriement de la fille en Roumanie ( cf. supra consid. 5.1, 6.2.1 et 6.3.1). Dès lors qu'il apparaît que ces exceptions ne sont en définitive pas satisfaites ( cf. supra consid. 5.3, 6.2.3 et 6.3.3), de même que celle de l'art. 13 al. 2 CLaH80 ( cf. supra consid. 7.1.3), il convient d'examiner si l'hypothèse visée par l'art. 13 al. 1 let. b CLaH80 est réalisée et conduirait au rejet de la demande en retour de l'enfant.
7.2.1. En vertu de l'art. 13 al. 1 let. b CLaH80, l'autorité judiciaire de l'État requis n'est pas tenue d'ordonner le retour de l'enfant lorsque la personne qui s'oppose à son retour établit qu'il existe un risque grave que ce retour n'expose l'enfant à un danger physique ou psychique, ou de toute autre manière ne le place dans une situation intolérable. Seuls des risques graves doivent être pris en considération, à l'exclusion de motifs liés aux capacités éducatives des parents, dès lors que la CLaH80 n'a pas pour but de statuer au fond sur le sort de l'enfant, notamment sur la question de savoir quel parent serait le plus apte à l'élever et à prendre soin de lui; la décision à ce sujet revient au juge du fait de l'État de provenance et la procédure de retour tend uniquement à rendre possible une décision future à ce propos ( cf. art. 16 et 19 CLaH80; <ref-ruling> consid. 2.4; <ref-ruling> consid. 5.3; arrêt 5A_705/2014 du 15 octobre 2014 consid. 4.1 et les références citées).
L'<ref-law> précise l'application de l'art. 13 al. 1 let. b CLaH80, en énumérant une série de cas dans lesquels le retour de l'enfant ne peut plus entrer en ligne de compte parce qu'il placerait celui-ci dans une situation manifestement intolérable (Message concernant la mise en oeuvre des conventions sur l'enlèvement international d'enfants ainsi que l'approbation et la mise en oeuvre des conventions de La Haye en matière de protection des enfants et des adultes, du 28 février 2007, FF 2007 p. 2433, n° 6.4). Le retour de l'enfant ne doit pas être ordonné notamment lorsque: 1° le placement auprès du parent requérant n'est manifestement pas dans l'intérêt de l'enfant; 2° le parent ravisseur, compte tenu des circonstances, n'est pas en mesure de prendre soin de l'enfant dans l'État dans lequel l'enfant avait sa résidence habituelle au moment de l'enlèvement ou que l'on ne peut manifestement pas l'exiger de lui; 3° le placement auprès de tiers n'est manifestement pas dans l'intérêt de l'enfant (arrêts 5A_479/2012 du 13 juillet 2012 consid. 5.1, publié in PJA 2012 p. 1630 et in SJ 2013 I p. 29; 5A_583/2009 du 10 novembre 2009 consid. 4, publié in SJ 2010 I p. 151). Les conditions posées à l'<ref-law> n'ont pour objet que de clarifier les dispositions conventionnelles, et non pas de se substituer à elles. Le terme «notamment» signifie que ne sont énumérés que quelques cas de figure qui - bien qu'essentiels - n'empêchent pas que l'on se prévale de la clause prévue dans la convention (Message précité, FF 2007 p. 2433, n° 6.4).
7.2.2. L'état de fait de la décision entreprise laisse apparaître que le père a des antécédents judiciaires, consomme fréquemment de l'alcool et des stupéfiants, a une prédisposition au scandale, et a manifesté de la violence verbale et physique à l'encontre de son ex-femme. Il ressort aussi des faits que le tribunal de première instance roumain a exposé que, à la suite du traumatisme crânien subi en avril 2015, le père n'était plus à même de prendre soin de sa fille. Au vu de ces constatations, il y a lieu de s'interroger sur l'aptitude du père à prendre soin de sa fille, sans mettre l'intérêt et le bien-être de celle-ci, autrement dit, sans créer un risque concret et grave pour le développement de l'enfant. A tout le moins la réalisation de cette exception n'est-elle pas d'emblée exclue. En tant que cour suprême, le Tribunal fédéral est juge du droit - il statue sur la base des faits établis par l'autorité précédente (<ref-law>; cf. supra consid. 4.1) -, et, non juge du fait (arrêt 5A_339/2015 du 18 novembre 2015 consid. 2.3) et ne disposant manifestement pas de tous les éléments lui permettant de trancher cet aspect, la cour de céans n'est pas en mesure d'examiner cet aspect. Il convient dès lors de renvoyer la cause au juge de l'instance cantonale unique (<ref-law>; cf. supra consid.1) aux fins qu'il établisse les faits en relation avec l'éventuelle réalisation de l'exception de l'art. 13 al. 1 let. b CLaH80, puis qu'il statue à nouveau sur la cause, en particulier sur la réalisation de l'une des exceptions de l'art. 13 al. 1 let. a et b CLaH80.
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 :
1.
Le recours est admis, la décision attaquée est annulée et la cause est renvoyée à l'autorité cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Une indemnité de 1'500 fr., à payer au recourant, à titre de dépens pour l'instance fédérale, est mise à la charge de l'intimée.
4.
Une indemnité de 1'000 fr. est allouée à Me Gabrielle Weissbrodt, curatrice de l'enfant, à titre d'honoraires, qui lui sera payée par la Caisse du Tribunal fédéral.
5.
Le présent arrêt est communiqué aux parties, à l'enfant mineur par sa curatrice de représentation, au Juge unique de la Cour civile II du Tribunal cantonal du canton du Valais et à l'Autorité centrale en matière d'enlèvement international d'enfants de l'Office fédéral de la justice.
Lausanne, le 13 septembre 2016
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : von Werdt
La Greffière : Gauron-Carlin