Faits : A. A.a. B._, née en 1976, et A._, né en 1975, tous deux de nationalité française, sont les parents non mariés de l'enfant C._, né en 2013 à Paris. Ils exercent en commun l'autorité parentale sur leur fils, qu'ils ont reconnu le 15 janvier 2013 à Paris devant l'officier de l'état civil. Le 16 septembre 2014, ils ont signé une convention de pacte civil de solidarité (PACS) de droit français auprès du Tribunal d'instance de Paris. A.b. Le 1er juin 2014, B._ et A._ se sont installés à U._, ce dernier ayant trouvé un emploi dans la région lausannoise. B._ a alors quitté son travail en France pour suivre son compagnon en Suisse avec leur enfant C._. A.c. Dès son arrivée en Suisse, B._ a entrepris des démarches pour trouver un emploi. Celles-ci demeurant vaines, elle s'est exclusivement consacrée à l'éducation de son fils, se rendant souvent avec ce dernier à Paris où il est régulièrement suivi depuis sa naissance par un pédiatre et où vit sa famille dont elle est très proche. En juin 2015, confrontée à des difficultés de couple et se sentant isolée en Suisse, B._ s'est inscrite à un concours organisé par la Mairie de W._ en vue de l'obtention d'un poste de secrétaire dans l'administration. Le 4 février 2016, elle a appris de la Direction des ressources humaines de la Mairie de W._ qu'elle avait été admise au concours et qu'elle avait obtenu le poste escompté, avec entrée en fonction le 1er avril 2016. A.d. Début 2015, A._ a perdu son emploi, mais a caché à sa compagne son licenciement en faisant semblant, durant trois mois, de se rendre sur son lieu de travail. Dès le 29 juillet 2015, il a perçu des indemnités de l'assurance-chômage (son délai-cadre échoit le 28 juillet 2017); en septembre 2015, il a postulé à quatre reprises pour des emplois à Paris. A.e. Le 6 janvier 2016, B._ et A._ ont résilié le bail à loyer de leur appartement sis à U._. Par lettre du 8 janvier 2016, la bailleresse a accusé réception de la résiliation, mais les a informés que la prochaine échéance légale de leur contrat était le 30 juin 2016. A.f. Les tensions dans le couple n'ont cessé de croître, nécessitant l'intervention de la force publique. En novembre 2015, A._ a enfermé sa compagne sur le balcon et a fait une tentative de suicide avec une corde d'escalade, alors que l'enfant était présent dans l'appartement. Le 5 février 2016, confrontée à un épisode de violence physique, B._ a fait appel aux forces de l'ordre qui l'a conduite avec son fils au Centre d'accueil V._. B. B.a. Le 4 février 2016, A._ a adressé à la Justice de paix du district de l'Ouest lausannois une lettre ayant pour objet " déclaration préliminaire avec pour but d'entamer conciliation ou séparation et assurer les droits de C._, A._ et B._ ". B.b. Par requête de mesures superprovisionnelles et provisionnelles du 9 février 2016, B._ a conclu à ce que le droit de déterminer le lieu de résidence de l'enfant C._ lui soit confié et à l'autorisation de déplacer le domicile de l'enfant à Paris, sous réserve de l'exercice par A._ d'un droit de visite médiatisé (deux heures à quinzaine, le samedi, par l'intermédiaire de l'Institution D._ à Paris, avec interdiction de sortir des locaux). B.c. Statuant par voie d'urgence le 10 février 2016, la Juge de paix du district de l'Ouest lausannois (ci-après: Juge de paix) a interdit le changement du lieu de résidence de l'enfant C._ vers la France, dit que B._ était seule détentrice de la garde de l'enfant, que A._ exercerait son droit de visite sur son fils par l'intermédiaire de Point Rencontre deux fois par mois pour une durée maximale de deux heures, à l'intérieur des locaux exclusivement, en fonction du calendrier d'ouverture et conformément au règlement et principes de fonctionnement qui sont obligatoires pour les deux parents, charge à eux de prendre contact avec l'association pour un entretien préalable à la mise en place des visites. B.d. Par ordonnance de mesures provisionnelles du 10 mars 2016, la Juge de paix a notamment ouvert une enquête en attribution du droit de déterminer le lieu de résidence de l'enfant C._ (I); dit qu'un mandat d'évaluation sera confié au Service de protection de la jeunesse (SPJ) (II); interdit provisoirement le changement du lieu de résidence de l'enfant C._ vers la France (III); dit que B._ est provisoirement détentrice de la garde de l'enfant (IV); dit que A._ exercera provisoirement son droit de visite sur C._ par l'intermédiaire de Point Rencontre deux fois par mois, pour une durée maximale de deux 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 (V); dit que Point Rencontre reçoit une copie de la décision, détermine le lieu des visites et en informe les parents par courrier, avec copies aux autorités compétentes (VI); dit que chacun des parents est tenu de prendre contact avec le Point Rencontre désigné pour un entretien préalable à la mise en place des visites (VII); et exhorté B._ et A._ à débuter immédiatement une médiation afin de rétablir la communication et la confiance entre eux et leur permettre de prendre ensemble des décisions conformes au bien-être et au bon développement de leur enfant et ce malgré leur séparation (VIII). B.e. Par acte du 21 mars 2016, B._ a recouru devant le Tribunal cantonal vaudois contre cette ordonnance. Elle a conclu, principalement, à sa réforme en ce sens que le droit de déterminer le lieu de résidence de l'enfant C._ est confié à sa mère auprès de laquelle il résidera, qu'elle est autorisée à déplacer le domicile de l'enfant à Paris et que A._ pourra exercer ses relations personnelles sur son fils par l'intermédiaire du Point Rencontre D._ à Paris, durant deux heures à quinzaine, le samedi, avec interdiction de sortir des locaux. Subsidiairement, elle a conclu à l'annulation de l'ordonnance et à son renvoi à l'autorité de première instance pour nouvelle décision dans le sens des considérants. B.f. Par avis recommandé du 24 mars 2016, la Chambre des curatelles du Tribunal cantonal vaudois (ci-après: Chambre des curatelles) a notifié à A._ un exemplaire du recours et lui a imparti un délai non prolongeable de 10 jours pour déposer une réponse. B.g. Dans sa réponse du 11 avril 2016, A._ a conclu au rejet du recours. B.h. Par arrêt du 12 avril 2016, la Chambre des curatelles a admis le recours de B._ et a réformé les chiffres III et V du dispositif de l'ordonnance attaquée en ce sens que B._ est autorisée provisoirement à déplacer le lieu de résidence de l'enfant C._ à Paris et que A._ exercera provisoirement son droit de visite sur C._ par l'intermédiaire du Point Rencontre D._ à Paris, deux samedis par mois (les 2èmeet 4ème samedis), pour une durée maximale de deux 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. L'ordonnance querellée a été confirmée pour le surplus. Les parties ont été informées du dispositif de l'arrêt du 12 avril 2016 par avis recommandé du 13 avril 2016. L'expédition complète de l'arrêt a été notifiée le 20 avril 2016. C. Par acte déposé le 27 avril 2016, A._ exerce un recours en matière civile au Tribunal fédéral contre l'arrêt du 12 avril 2016. Il conclut à son annulation et au renvoi de la cause à l'autorité précédente pour nouvelle décision. Il se plaint uniquement de la violation de son droit d'être entendu (art. 29 al. 2 Cst.). Invitée à se déterminer sur la requête d'effet suspensif assortissant le recours, l'intimée a conclu à son rejet. Sur le fond, la cour cantonale s'est référée aux considérants de son arrêt et l'intimée a conclu principalement à l'irrecevabilité et, subsidiairement, au rejet du recours. D. Par ordonnance présidentielle du 9 mai 2016, la requête d'effet suspensif a été admise. E. Le 7 juillet 2016, le Tribunal fédéral a tenu une audience de débats, lors de laquelle les conseils des parties ont plaidé, persistant dans leurs conclusions respectives. Dans le cadre de sa plaidoirie, le conseil du recourant a allégué que, nonobstant la décision de première instance et l'effet suspensif octroyé par le Tribunal fédéral, l'intimée avait d'ores et déjà déménagé en France avec l'enfant, ce que le conseil de l'intimée a contesté. L'affaire a ensuite été délibérée en séance publique.