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'art. 292 CP 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'art. 308 CC 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'art. 308 CC. 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'art. 308 CC. 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'art. 308 al. 1 CC, 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'art. 308 al. 2 CC (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'art. 292 CP, 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'art. 308 al. 1 CC, 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'art. 308 al. 2 CC. 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.