Faits :
A.
A.a. B.A._, née à Pékin mais ayant acquis la nationalité française en 2006, et A.A._, de nationalité française, se sont mariés le 9 août 2008 à Paris. De cette union est née C._, le 31 juillet 2009, à Y._. Le couple vivait alors à U._. Il a ensuite déménagé à V._, dans le canton de Zurich. C._ a été régulièrement confiée à la garde de ses grands-parents paternels en France en raison des activités et nombreux voyages professionnels des parents, lesquels ont connu dès 2010 des tensions. Le couple a vécu séparé depuis la mi-mars 2012.
A.b. Le 10 mai 2012, B.A._ est allée chercher sa fille auprès de ses grands-parents paternels en France et s'est installée avec elle dans un appartement loué à W._ (ZH). Elle a en outre introduit une procédure de mesures protectrices de l'union conjugale auprès du Tribunal de E._ (ZH).
A.c. Le 25 mai 2012, A.A._ a déposé plainte auprès du Procureur de la République de F._ (France) contre son épouse pour soustraction d'un mineur des mains de ceux chargés de sa garde. Le 1er juin 2012, il a en outre déposé auprès du Tribunal de Grande Instance de Paris une requête en divorce.
A.d. Le 9 juillet 2012, A.A._ a formé auprès du tribunal compétent du canton de Zurich une demande de retour de l'enfant. Par arrêt du 24 juillet 2012, l'Obergericht du canton de Zurich a ordonné le retour de l'enfant C._ en France.
A.e. A.A._ a loué dès le 1er août 2012 un appartement meublé de 5,5 pièces à U._. Il a inscrit C._ dès le mois de septembre 2012 à une garderie de X._.
A.f. Par ordonnance de non-conciliation du 23 octobre 2012, la Juge aux affaires familiales du Tribunal de Grande Instance de Paris a, conformément à l'accord des époux sur ce point, dit que l'autorité parentale sur l'enfant sera exercée en commun par les parents et que la résidence habituelle de l'enfant sera au domicile du père. La juge a encore dit que le droit de visite de la mère s'exercera une fin de semaine sur deux du jeudi après la sortie des classes au dimanche à 19 heures, l'intégralité des vacances d'automne et d'hiver, la première moitié des autres vacances scolaires les années paires et la seconde moitié les années impaires, outre quinze jours pour le Nouvel An chinois. Elle a également constaté l'accord des parties pour interdire toute sortie de l'enfant hors du territoire de Schengen sans l'autorisation écrite des deux parents.
A.g. Le 4 octobre 2013, les parties ont signé une convention de divorce, par laquelle ils ont convenu que l'autorité parentale sur C._ resterait commune et que sa résidence serait fixée chez son père. Elles ont précisé que A.A._ résiderait à Singapour et B.A._ en Chine. Sauf meilleur accord, les parties ont prévu que le droit de visite de la mère s'exercerait durant la totalité des vacances du Nouvel An chinois, du printemps, de l'été, de l'automne et de l'hiver jusqu'au 20 décembre. Cette convention, transmise à l'appui d'une requête conjointe en divorce, n'a toutefois pas été homologuée par le juge français dès lors que la cause a été radiée du rôle suite au défaut de B.A._ à l'audience du 19 décembre 2013.
A.h. Selon un accord entre les parties, B.A._ devait avoir sa fille auprès d'elle du 19 novembre au 19 décembre 2013. L'intéressée a finalement pu prendre sa fille le 17 novembre 2013. Le 20 novembre suivant, elle s'est rendue en Allemagne chez sa soeur avec C._. Le 19 décembre 2013, elle n'a toutefois pas rendu l'enfant à son père. Le 26 décembre 2013, A.A._ a déposé plainte pénale contre B.A._ pour enlèvement de mineur. Le 3 janvier suivant, il a en outre adressé aux autorités allemandes une demande de retour de l'enfant en Suisse. Par décision du 7 janvier 2014, l' " Amtsgericht Frankfurt am Main " a déclaré que A.A._ et B.A._ n'étaient pas autorisés à quitter l'Allemagne, respectivement le territoire de Schengen, avec leur enfant C._, ni à permettre à toute autre personne de quitter la pays avec l'enfant. C._ a regagné la Suisse avec son père le 16 janvier 2014.
B.
B.a. Le 28 janvier 2014, A.A._ a formé devant le Tribunal d'arrondissement de La Côte une " action en fixation des droits parentaux ", avec requête de mesures superprovisionnelles.
B.b. Par ordonnance de mesures superprovisionnelles du 29 janvier 2014, le Président du Tribunal civil de l'arrondissement de La Côte (ci-après: Président du Tribunal) a confié la garde sur l'enfant C._ à son père (I), dit que l'exercice du droit de visite de B.A._ sur sa fille s'exercera par l'intermédiaire de Point Rencontre deux fois par mois, pour une durée maximale de 2 heures, à l'intérieur des locaux exclusivement, en fonction du calendrier d'ouverture et conformément au règlement et aux principes de fonctionnement de Point Rencontre, qui sont obligatoires pour les deux parents (II), ordonné à B.A._ de remettre immédiatement à A.A._, par pli postal avec accusé de réception, tous les documents d'identité de l'enfant qui sont en sa possession, en particulier le passeport français et le permis B suisse, ainsi que le carnet de santé (III), interdit à B.A._ de circuler librement avec sa fille, de quitter le territoire suisse avec elle et de circuler dans un rayon de 500 mètres autour de l'école et du domicile de C._, sous la menace de la peine prévue par l'<ref-law> pour insoumission à une décision de l'autorité (IV à VI).
B.c. Par ordonnance de mesures provisionnelles du 9 juillet 2014, le Président du Tribunal a confirmé les chiffres II et III de l'ordonnance de mesures superprovisionnelles rendue le 29 janvier 2014 (I), a dit que, pour le surplus, les chiffres I et IV à VI de l'ordonnance de mesures superprovisionnelles rendue le 29 janvier 2014 restent valables jusqu'à droit connu sur les conclusions provisionnelles sur lesquelles l'instruction a été suspendue, a rendu le passeport de l'enfant C._ à A.A._, ceci par l'intermédiaire de son conseil (III), a chargé le Service de psychiatrie de l'enfant et de l'adolescent de réaliser une expertise pédopsychiatrique de l'enfant C._ (IV), et a confié au Service de protection de la jeunesse (SPJ) un mandat d'évaluation de la situation de l'enfant C._ (V).
B.d. Par arrêt du 26 août 2014, la Juge déléguée de la Cour d'appel civile du Tribunal cantonal vaudois a rejeté l'appel formé par B.A._ et a confirmé l'ordonnance du 9 juillet 2014.
C.
C.a. Le SPJ a rendu son rapport d'évaluation le 14 juillet 2015, aux termes duquel il a proposé d'élargir le droit de visite de la mère à 6 heures hors des locaux de Point Rencontre avec dépôt de son passeport pendant ce laps de temps, d'attribuer par la suite un droit de visite usuel à la mère sur sa fille C._ si rien ne s'y oppose dans les conclusions de l'expertise pédopsychiatrique, de lui attribuer un mandat au sens de l'art. 308 al. 1 et 2 CC afin que la mère ait quelqu'un vers qui se tourner en cas de difficultés, pour s'assurer du bon déroulement du droit de visite et pour s'assurer qu'un suivi pédopsychiatrique pour C._ soit institué sur le long terme, et de faire en sorte que la mère puisse communiquer avec sa fille deux fois par semaine.
C.b. Le 29 septembre 2015, la Dresse D._, spécialiste FMH en psychiatrie et psychothérapie pour enfants et adolescents, a rendu son rapport d'expertise pédopsychiatrique. L'experte préconise notamment d'imposer à chacun des parents de tenir compte de l'autre dans l'organisation de leur propre vie. Devant le risque d'une perpétuation du conflit autour du choix du lieu de vie, il semblait réaliste de leur imposer un lieu de vie proche du lieu de vie actuel de C._, pour au moins une dizaine d'années. Idéalement, une reprise plus régulière des contacts avec la mère devrait s'organiser et, si cela se passe bien, une organisation plus juste du temps passé avec chacun des parents devrait se mettre en place. Dans ce sens, une curatelle au sens de l'<ref-law> apparaissait indispensable. Il était également indispensable que B.A._ bénéficie d'un soutien thérapeutique. A.A._ devrait, quant à lui, rechercher au moins un appui éducatif. C._ devrait de son côté être suivie régulièrement par un psychothérapeute d'enfants, à raison de deux fois par semaine.
C.c. Par requête de mesures provisionnelles et superprovisionnelles formée le 4 novembre 2015 devant le Tribunal d'arrondissement de La Côte, B.A._ a notamment pris les conclusions suivantes:
" (...) par voie de mesures provisionnelles :
I. Dès le 1er janvier 2016, B.A._ pourra exercer son droit de visite sur sa fille C._ un week-end par mois du jeudi soir 18h00 au dimanche soir 18h00, à charge pour elle d'aller chercher l'enfant là où elle se trouve et de l'y ramener.
Elle pourra également avoir C._ auprès d'elle durant quinze jours de vacances consécutives, qui devront être fixées trois mois à l'avance au minimum. Par ailleurs, les vacances devront être exercées durant les vacances scolaires de l'enfant.
II. B.A._ pourra en outre contacter sa fille deux fois par semaine pendant deux heures chaque fois, par l'intermédiaire de Skype. "
C.d. Le 6 novembre 2015, le Président du Tribunal a rejeté la requête de mesures superprovisionnelles.
C.e. A l'audience du 6 janvier 2016, B.A._ a modifié sa conclusion provisionnelle I, 2ème paragraphe, remplacé par le paragraphe suivant: " Elle pourra également avoir sa fille C._ auprès d'elle durant la moitié des vacances scolaires, vacances qu'elle pourra effectuer avec sa fille, y compris à l'étranger. " Elle a en outre adhéré aux conclusions de l'experte pédopsychiatre et du SPJ tendant à l'instauration d'une curatelle au sens de l'<ref-law>.
A.A._ a conclu au maintien du Point Rencontre tel qu'exercé actuellement et à ce qu'il soit renoncé à instaurer une curatelle au sens de l'<ref-law>.
A dite audience, les parties ont en outre signé une convention partielle, ratifiée séance tenante pour valoir ordonnance partielle de mesures provisionnelles, dont la teneur est la suivante: " I. En marge du litige qui les oppose et sur lequel elles ont pris des conclusions, les parties conviennent que B.A._ communiquera avec sa fille C._ via Skype tous les dimanches de 9h00 à 10h00, cela dès le 10 janvier 2016. "
C.f. Par ordonnance de mesures provisionnelles du 19 février 2016, le Président du Tribunal a notamment confirmé le chiffre I de l'ordonnance de mesures superprovisionnelles rendue le 29 janvier 2014, en ce sens que la garde sur l'enfant C._ est confiée à son père (I), instauré une curatelle d'assistance éducative au sens de l'<ref-law>, avec la mission de soutenir A.A._ et d'assurer la poursuite du traitement psychothérapeutique de l'enfant C._, et une curatelle de surveillance du droit aux relations personnelles au sens de l'<ref-law> (III), dit que l'exercice du droit de visite de la mère sur sa fille C._ s'exercera une fois par mois du jeudi après l'école jusqu'au dimanche soir selon un planning qui sera établi par le curateur (Va), astreint B.A._ à déposer son passeport auprès de A.A._ lors de l'exercice du droit de visite, à défaut de quoi A.A._ sera autorisé à ne pas lui remettre l'enfant C._ (Vb), dit que, jusqu'à l'établissement du planning, le droit de visite continuera à s'exercer conformément à l'ordonnance de mesures provisionnelles du 9 juillet 2014 (Vc), interdit à B.A._ de quitter le territoire suisse avec sa fille C._, sous la menace de la peine prévue à l'<ref-law>, et a révoqué pour le surplus le chiffre II de l'ordonnance de mesures provisionnelles rendue le 9 juillet 2014.
Le Président du Tribunal a notamment jugé que vu l'importance des troubles psychologiques de l'enfant, son besoin établi de développer des contacts avec sa mère et les difficultés du père à reconnaître ce besoin, il se justifiait d'instaurer une curatelle d'assistance éducative au sens de l'<ref-law>, avec mission de soutenir le père et d'assurer la poursuite du traitement psychothérapeutique de l'enfant. En outre, vu les difficultés récurrentes des parents à s'entendre sur les modalités d'exercice du droit de visite de la mère, il y avait également lieu d'instaurer une curatelle de surveillance du droit aux relations personnelles au sens de l'<ref-law>.
Le Président du Tribunal a par ailleurs fait siennes les constatations de l'experte pédopsychiatre et du SPJ sur la nécessité pour l'enfant de développer rapidement des contacts avec sa mère et sur le fait que le droit de visite peut s'exercer en dehors du cadre médiatisé du Point Rencontre, dans la mesure où la mère se comporte de manière adéquate avec son enfant et où il n'existe aucun indice raisonnable de maltraitances physiques ou psychologiques de la part de celle-ci. Il y avait donc lieu de lever la mesure de droit de visite surveillé au Point Rencontre. En revanche, s'agissant du risque d'enlèvement de l'enfant, le Président du Tribunal a indiqué qu'il ne pouvait suivre les conclusions de l'experte pédopsychiatre, qui considérait ce risque comme étant inexistant. A deux reprises en effet, soit en 2012 et en 2013, la mère avait déplacé l'enfant sans l'accord du père, respectivement ne l'avait pas remis à son père au terme de la période prévue pour le droit de visite. Dans les deux cas, le père avait dû faire appel aux autorités pour obtenir le retour de l'enfant. L'experte pédopsychiatre expliquait ce comportement par le fait que la mère était démunie face à une situation qui lui échappait et qu'elle avait été malmenée physiquement, à une reprise en tout cas, par son beau-père, voire par son mari. Le désarroi de la mère, compréhensible, ne devait toutefois pas faire oublier que par son comportement, elle avait porté atteinte de manière réitérée au droit de garde du père, de manière délibérée et d'une manière indirectement préjudiciable à l'enfant. Elle avait ainsi manifesté clairement son intention de violer ses devoirs et s'était livrée à des actes de justice propre pour obtenir par la force ce qu'elle aurait dû requérir par la voie judiciaire. Au surplus, l'arrêt du Tribunal cantonal vaudois du 26 août 2014 retenait que le risque d'enlèvement de l'enfant apparaissait bien concret. Il convenait encore de relever que la mère avait fréquemment changé de lieu de séjour ces dernières années (France, Suisse, Allemagne, Suisse puis Thaïlande depuis début 2015), ce qui révélait chez elle une certaine instabilité justifiant d'apprécier la situation avec une prudence accrue. Enfin, on ignorait tout du suivi thérapeutique de la mère et notamment de son impact sur son aptitude à respecter le cadre de son droit de visite fixé judiciairement. Compte tenu de ces éléments, il y avait lieu de considérer que le risque de " déplacement " de l'enfant contre l'avis du père restait concret. Il convenait ainsi de garantir que la mère remettra l'enfant au terme des périodes de visite prévues et ne cherchera pas à l'enlever.
C.g. Les deux parties ont formé appel de cette ordonnance devant le Tribunal cantonal vaudois.
C.h. Dans son appel du 3 mars 2016, A.A._ a formé une requête d'effet suspensif, dont les conclusions sont les suivantes:
" I. L'exécution de l'ordonnance de mesures provisionnelles rendue par le Président du Tribunal civil d'arrondissement de La Côte le 19 février 2016 (...) est suspendue jusqu'à l'entrée en force de la décision sur appel;
II. L'ordonnance de mesures provisionnelles rendue par le Président du Tribunal civil d'arrondissement de La Côte le 9 juillet 2014 est maintenue jusqu'à l'entrée en force de la décision sur appel.
III. En tant que de besoin, une contre-ordonnance est mise en oeuvre. "
C.i. Par décision du 4 mars 2016, la Juge déléguée de la Cour d'appel civile du Tribunal cantonal vaudois a rejeté la requête d'effet suspensif.
D.
D.a. Par acte posté le 6 avril 2016, A.A._ exerce un recours en matière civile au Tribunal fédéral contre la décision du 4 mars 2016. Il conclut à son annulation et à sa réforme dans le sens des conclusions I et II de la requête d'effet suspensif assortissant son appel cantonal.
D.b. Le 25 avril 2016, A.A._ a requis des mesures superprovisionnelles et provisionnelles tendant à ce que l'exécution de l'ordonnance de mesures provisionnelles du 19 février 2016 est suspendue jusqu'à droit jugé sur son recours du 6 avril 2016.
Le Président de la IIe Cour de droit civil du Tribunal fédéral a fait droit à la requête de mesures superprovisionnelles par ordonnance du 26 avril 2016.
Invitée à se déterminer sur la requête de mesures provisionnelles, B.A._ a conclu à son rejet et a sollicité d'être mise au bénéfice de l'assistance judiciaire pour la procédure fédérale.
Par ordonnance présidentielle du 3 mai 2016, la requête de mesures provisionnelles a été admise et l'ordonnance de mesures superprovisionnelles du 26 avril 2016 confirmée.
Des observations sur le fond n'ont pas été requises.

Considérant en droit :
1.
1.1. La décision querellée, qui refuse de suspendre l'exécution d'une ordonnance de mesures provisionnelles portant notamment sur l'exercice du droit de visite de la mère sur un enfant mineur, contre lequel un appel a été formé, constitue une décision incidente en matière civile (<ref-law>; <ref-ruling> consid. 1 p. 476).
Hormis les décisions mentionnées à l'<ref-law>, une décision préjudicielle ou incidente ne peut être entreprise immédiatement que si elle peut causer un préjudice irréparable (<ref-law>) ou si l'admission du recours peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse (<ref-law>; <ref-ruling> consid. 1.3 p. 127). En l'occurrence, l'arrêt entrepris est susceptible de causer au recourant un dommage irréparable, puisque les droits parentaux sont arrêtés pour la durée de la procédure; même s'il obtient finalement gain de cause au fond, aucune réparation ne sera possible pour la période écoulée (<ref-ruling> précité consid. 1 p. 477 et les références).
Le Tribunal cantonal vaudois n'a pas statué sur recours mais en qualité d'instance cantonale unique sur l'effet suspensif requis dans le cadre d'une procédure d'appel; le recours en matière civile est cependant admissible en vertu de l'<ref-law> (<ref-ruling> consid. 1.1 p. 42; <ref-ruling> consid. 2.2 p. 426).
1.2. Le recours contre une décision incidente est soumis à la même voie de droit que celle qui est ouverte contre la décision principale (<ref-ruling> consid. 1.1 p. 382). La cause pour laquelle l'effet suspensif est requis se rapporte en l'espèce à une procédure en fixation des droits parentaux. Le litige est ainsi de nature non pécuniaire. Le recours en matière civile a en outre été interjeté dans le délai (<ref-law>) et en la forme (<ref-law>) prévus par la loi, de sorte qu'il est en principe recevable.
2.
2.1. La décision refusant l'effet suspensif, comme celle d'exécution provisoire, et celle de retrait ou d'octroi de l'effet suspensif (<ref-ruling> consid. 2 p. 477), est une décision portant sur des mesures provisionnelles au sens de l'<ref-law>, de sorte que seule peut être invoquée la violation de droits constitutionnels. Le Tribunal fédéral n'examine de tels griefs que s'ils ont été invoqués et motivés conformément au principe d'allégation (<ref-law>), à savoir expressément soulevés et exposés de manière claire et détaillée (<ref-ruling> consid. 2.2 p. 232; <ref-ruling> consid. 3.3 p. 310). Il n'entre pas en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 2.3 p. 266; <ref-ruling> consid. 10.1 p. 445).
En particulier, une décision ne peut être qualifiée d'arbitraire (art. 9 Cst.) que si elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté, ou heurte de manière choquante le sentiment de la justice et de l'équité; il ne suffit pas qu'une solution différente apparaisse concevable, voire préférable; pour que cette décision soit annulée, encore faut-il qu'elle se révèle arbitraire, non seulement dans ses motifs, mais aussi dans son résultat (<ref-ruling> consid. 2.1 p. 18 s.; <ref-ruling> consid. 3.2.5 p. 339; <ref-ruling> consid. 7.1 p. 51, 305 consid. 4.3 p. 319; <ref-ruling> consid. 6.1 p. 379 s.; <ref-ruling> consid. 2.4 p. 5; <ref-ruling> consid. 2.2.2 p. 318 s.).
2.2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>) et de ceux retenus par la juridiction inférieure, dans la mesure où ces faits sont repris implicitement dans la décision attaquée (arrêts 4A_150/2015 du 29 octobre 2015 consid. 1.2; 4A_247/2013 du 14 octobre 2013 consid. 1.1; sous l'OJ: <ref-ruling> consid. 1 p. 248).
En l'espèce, la décision attaquée ne comporte aucun exposé des faits de la cause et apparaît ainsi insuffisamment motivée à l'aune de l'<ref-law>, qui impose notamment à l'autorité cantonale d'exposer l'état de fait sur lequel elle se fonde et le raisonnement juridique qui a été suivi (<ref-ruling> consid. 8.2 p. 153). Dans la mesure toutefois où la Juge déléguée se réfère à l'ordonnance de mesures provisionnelles du 19 février 2016, il y a lieu - à titre exceptionnel et pour éviter un renvoi prolongeant inutilement la procédure - d'admettre qu'elle en reprend implicitement l'état de fait. Les faits de la présente cause ont donc été complétés sur la base de cette ordonnance et des pièces du dossier auxquelles elle renvoie.
3.
Le recourant se plaint d'arbitraire dans l'application de l'<ref-law>. A l'appui de son grief, il reproche à la Juge déléguée de s'être écartée de manière arbitraire de la jurisprudence du Tribunal fédéral - en particulier de l'arrêt 5A_438/2015 du 25 juin 2015 -, soutenant que l'existence d'un risque de préjudice difficilement réparable est avérée. Selon l'ordonnance rendue par le Président du Tribunal, il existait en l'état un risque concret d'enlèvement de C._ par sa mère. La décision entreprise indiquait du reste que ce risque devait être fortement relativisé, admettant ainsi qu'il existe. Au demeurant, les éléments retenus par l'autorité cantonale pour " relativiser " ce risque étaient contraire à l'arrêt 5A_438/2015. Il ressortait en effet de cet arrêt que le dépôt des documents d'identité et de voyage de l'enfant et du parent exerçant le droit de visite, ainsi que l'interdiction de quitter le territoire suisse, ne permettaient pas de parer au risque d'enlèvement d'enfant, soit de préjudice difficilement réparable au sens de l'<ref-law>. A cela s'ajoutait que dans cet arrêt, une mise en danger concrète de la mineure n'était même pas clairement établie. Ce risque se fondait en effet uniquement sur les nationalités étrangères du parent exerçant le droit de visite et sur la présence de sa famille à l'étranger.
En l'occurrence, le risque d'enlèvement de C._ avait été reconnu comme étant concret par le premier juge et était étayé par les deux tentatives d'enlèvement dont l'intimée s'était rendue coupable, ainsi que son domicile et ses projets d'avenir en Thaïlande. Cette dernière avait en outre également déposé un appel contre l'ordonnance du 19 février 2016 afin de requérir à nouveau qu'elle puisse exercer son droit de visite en Thaïlande.
La décision entreprise semblait surtout motivée par la volonté de permettre à C._ de bénéficier rapidement de contacts plus intenses avec sa mère, la Juge déléguée se référant à cet effet principalement à l'expertise pédopsychiatrique. Or, cette expertise avait été relativisée par le premier juge et était contestée par le recourant dans le cadre de son appel. Par ailleurs, les conclusions du SPJ favorisaient un élargissement progressif du droit de visite et non une modification précipitée de ses modalités. La requête d'effet suspensif n'empêchait nullement l'intimée de bénéficier de contacts réguliers avec C._ puisqu'elle a pour conséquence de maintenir le statu quo et l'exercice par l'intimée d'un droit de visite deux fois par mois au sein du Point Rencontre. A cela s'ajoutait que si le risque d'enlèvement devait se concrétiser, une mise en oeuvre des conventions internationales pour permettre le retour de C._ pourrait s'avérer particulièrement compliquée si l'enfant était déplacée en Thaïlande ou dans un autre pays d'Asie. On ne pouvait en outre exclure que l'intimée profite de l'ouverture des frontières dans l'espace Schengen pour disparaître avec C._ ou qu'elle dispose d'une manière ou d'une autre d'un second passeport.
3.1. L'appel n'a en principe pas d'effet suspensif lorsqu'il a pour objet des décisions portant sur des mesures provisionnelles (<ref-law>). En vertu de l'<ref-law>, l'exécution des mesures provisionnelles peut toutefois être exceptionnellement suspendue si la partie concernée risque de subir un préjudice difficilement réparable.
Le préjudice difficilement réparable peut être de nature factuelle; il concerne tout préjudice, patrimonial ou immatériel, et peut même résulter du seul écoulement du temps pendant le procès. Le dommage est constitué, pour celui qui requiert les mesures provisionnelles, par le fait que, sans celles-ci, il serait lésé dans sa position juridique de fond et, pour celui qui recourt contre le prononcé de telles mesures, par les conséquences matérielles qu'elles engendrent. Saisie d'une demande d'effet suspensif, l'autorité de recours doit faire preuve de retenue et ne modifier la décision de première instance que dans des cas exceptionnels; elle dispose cependant d'un large pouvoir d'appréciation permettant de tenir compte des circonstances concrètes du cas d'espèce (ATF <ref-ruling> consid. 6.3 p. 381; <ref-ruling> consid. 4.1 p. 478; arrêts 5A_403/2015 du 28 août 2015 consid. 5; 5A_419/2014 du 9 octobre 2014 consid. 7.1.2).
Dans la mesure où une décision sur le droit de visite est susceptible de causer un préjudice irréparable au sens de l'<ref-law> (cf. supra consid. 1.1), elle peut à plus forte raison entraîner un préjudice difficilement réparable au sens de l'<ref-law> (<ref-ruling> consid. 2 p. 384). Dans de tels cas, comme susmentionné, il appartient ainsi au juge saisi de procéder à une pesée des intérêts en présence en tenant compte des circonstances concrètes (arrêt 5A_861/2011 du 10 janvier 2012).
3.2. En l'espèce, la Juge déléguée a considéré que, dès lors que la décision attaquée tenait compte de la nécessité de prévenir le risque d'enlèvement de l'enfant du fait de la mère en prévoyant le dépôt du passeport de cette dernière préalablement à la remise de l'enfant et que les documents d'identité et de voyage de l'enfant sont en mains du père, seul titulaire du droit de déterminer le lieu de résidence de l'enfant, le risque de préjudice difficilement réparable invoqué à l'appui de la requête d'effet suspensif devait être " fortement relativisé ". Au surplus, il ressortait de la décision entreprise que l'intérêt de l'enfant C._ à bénéficier rapidement de contacts plus intenses avec sa mère était souligné tant par l'auteur de l'expertise pédopsychiatrique que par le SPJ. Cet intérêt devait prévaloir et s'opposait à l'octroi de l'effet suspensif requis.
3.3. Le recourant ne saurait tirer argument d'une précédente affaire jugée par le Tribunal de céans pour démontrer l'arbitraire de la décision querellée. L'arrêt 5A_438/2015 du 25 juin 2015 dont il se prévaut tient en effet compte des circonstances particulières du cas d'espèce et ne saurait être considéré comme ayant posé des principes applicables de manière générale. Il convient en particulier de relever que, dans l'arrêt cité par le recourant, l'enfant en question n'était âgée que de deux ans et demi et n'avait eu que très peu de contacts avec son père qu'elle n'avait pas vu du tout depuis trois mois lorsque la décision de première instance avait été rendue. La restitution partielle de l'effet suspensif au recours dirigé contre cette décision et, partant, le maintien du droit de visite du père au sein du Point Rencontre uniquement devait ainsi permettre de rétablir de manière progressive le lien père-fille qui avait été totalement interrompu durant plusieurs mois, étant précisé que les autorités cantonales étaient dans l'attente d'un rapport de l'enquêteur social à réception duquel le droit de visite du père devait être réévalué. La cour d'appel avait au surplus informé le Tribunal de céans qu'une décision au fond allait être rendue à brève échéance, de sorte que l'effet suspensif n'était restitué que pour une courte durée.
En l'espèce, la situation est différente. L'enfant C._ a toujours été régulièrement en contact avec sa mère depuis la séparation de ses parents. En outre, même si le recourant déclare avoir contesté cet aspect dans son appel interjeté contre l'ordonnance de mesures provisionnelles du 19 février 2016, il n'en demeure pas moins que la nécessité pour l'enfant de bénéficier de plus de contacts avec sa mère ressort autant de l'expertise pédopsychiatrique du 29 septembre 2015 que du rapport d'évaluation du SPJ du 14 juillet 2015 qui précise également que la solution du Point Rencontre n'est pas satisfaisante à long terme. Enfin, le recourant fait état du risque que l'enfant soit emmenée par sa mère en Thaïlande ou dans un autre pays d'Asie dans lesquels la mise en oeuvre de conventions internationales pour permettre le retour de l'enfant s'avère particulièrement compliquée. Or, dans la mesure où le recourant est en possession de tous les papiers d'identité de sa fille, ses craintes sur ce point sont infondées, ce indépendamment du fait que l'intimée dispose ou non d'un autre passeport que celui qu'elle doit déposer auprès de lui durant l'exercice de son droit de visite. A l'instar de ce qui avait été retenu dans l'arrêt cité par le recourant, on peut certes imaginer un déplacement de l'enfant au sein de l'espace Schengen même sans être en possession de son passeport. Cela étant, on peine en l'espèce à concilier les craintes du recourant sur ce point avec son propre comportement puisqu'il ressort de l'ordonnance de non-conciliation de la Juge aux affaires familiales du Tribunal de Grande Instance de Paris rendue le 23 octobre 2012, à savoir postérieurement au premier déplacement illicite de l'enfant C._, que les parties sont convenues de ne pas sortir l'enfant hors du territoire de Schengen sans l'autorisation écrite des deux parents. Le recourant avait alors au moins implicitement consenti à ce que l'intimée se déplace librement avec l'enfant au sein de l'espace Schengen, de sorte que son inquiétude actuelle à cet égard paraît difficilement explicable. En définitive, compte tenu des éléments qui précèdent, il apparaît que la cour cantonale n'a pas fait une application arbitraire de l'<ref-law> en refusant de restituer l'effet suspensif au recours du recourant.
4.
Sur le vu de ce qui précède, le recours doit être rejeté. Les frais judiciaires sont mis à la charge du recourant qui succombe au fond (<ref-law>). Il n'y a pas lieu d'allouer de dépens à l'intimée, qui n'a pas été invitée à répondre sur le fond et qui a conclu au rejet de la requête d'effet suspensif, alors que celle-ci a été admise. Les conditions de l'assistance judiciaire n'étant pas remplies (art. 64 al. 1 et 2 LTF), dès lors que sa position sur l'effet suspensif était d'emblée dénuée de chance de succès, le conseil de l'intimée n'a pas droit à une indemnité d'avocat d'office de ce chef.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
La requête d'assistance judiciaire de l'intimée est rejetée.
3.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué aux parties et à la Juge déléguée de la Cour d'appel civile du Tribunal cantonal du canton de Vaud.
Lausanne, le 6 juillet 2016
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : von Werdt
La Greffière : Hildbrand