Faits: A. A._, né en XXXX de nationalité belge, et B._, née en XXXX de nationalité belge, sont les parents de C._, née en 2003 à Z._ (Belgique), qui est également de nationalité belge. Selon l'accord portant sur les relations personnelles du requérant avec sa fille, ratifié par jugement du Tribunal de la jeunesse de Bruges du 3 avril 2008, les parents exercent l'autorité parentale conjointe sur l'enfant dont la résidence principale est à l'adresse de la mère et la résidence secondaire auprès du père. B. B.a. En 2011, B._ a décidé de s'établir en Suisse avec sa fille. Face à l'opposition du père, elle en a obtenu l'autorisation par jugement du Tribunal de la jeunesse de Bruges du 11 août 2011, l'exercice de l'autorité parentale conjointe sur l'enfant étant maintenue. Elle s'est installée à Lausanne avec l'enfant le 19 août 2011. B.b. Par arrêt du 2 avril 2012, la Cour d'appel de Gand a statué comme suit sur l'appel du père (selon la traduction du flamand produi-te par le recourant) : « Confirme le jugement attaqué dans la mesure où il statua que la mère pouvait déménager avec C._ en Suisse, que l'exercice conjoint de l'autorité parentale fut prévu et qu'il fut statué sur les frais et les dépens en première instance. Accorde au père un droit au contact personnel sur C._ pendant toute période de vacances entière telle que fixée en Suisse. Il faut qu'il s'agisse de vacances d'au moins 3 jours entiers, y compris les week-ends. Un jour de congé avant ou après le week-end constitue déjà une telle vacance. Les vacances commencent chez le père à midi du premier jour après le dernier jour de classe à 12h00 et se terminent le dernier jour avant le jour de classe suivant à 18h00. Le père a en outre contact avec C._ pendant le premier week-end de chaque mois, sauf pendant les mois de juillet et d'août, du vendredi 20h00 au dimanche 18h00. Le premier week-end du mois est chaque fois le premier week-end qui, vendredi samedi et dimanche compris, tombe dans le même mois. Tout le transport depuis et vers le père est à la charge de la mère. La mère fait savoir au père, au moins trois mois à l'avance, quand ont lieu les prochaines vacances en Suisse. Chaque mardi et jeudi, C._ peut - tant chez sa mère que chez son père - avoir contact avec l'autre parent entre 18h00 et 20h00 par téléphone ou par Skype ou d'une autre manière quelconque. Compense les indemnités de procédure en appel et laisse les autres dépens de l'appel à la charge de la partie qui les a exposés. » Ce jugement a été notifié à l'intimée en Suisse le 13 juin 2012. Il n'a pas fait l'objet d'un pourvoi en cassation. C. C.a. Le 18 juin 2012, la mère a formé une requête auprès de la Justice de paix du district de Lausanne visant à régler les relations personnelles entre l'enfant et son père, faisant valoir que celui-ci avait un rapport inadéquat et que le droit de visite arrêté par la Cour d'appel de Gand n'était pas compatible avec le bien de l'enfant. Elle a conclu à ce que le droit de visite du père sur sa fille s'exerce la moitié des vacances scolaires de l'enfant, en une ou deux semaines, sous réserve d'un préavis de deux semaines à la mère précisant où l'enfant passera ses vacances ainsi que trois jours alternativement à Noël, Pâques ou Pentecôte, durant l'Ascension ou le Jeûne fédéral, les frais de déplacement liés à l'exercice du droit de visite étant répartis par moitié entre les parents. À titre préprovisionnel, elle a conclu que A._ pourra avoir sa fille auprès de lui du samedi 7 juillet 2012 à 20.00 heures au jeudi 2 août à midi et, à titre provisionnel, que le droit de visite du père sur sa fille s'exerce la moitié des vacances scolaires de l'enfant, en une ou deux semaines, sous réserve d'un préavis de deux semaines à la mère précisant où l'enfant passera ses vacances, les frais de déplacement étant répartis par moitié entre les parties. C.b. Par ordonnance du 20 juin 2012, le Juge de paix du district de Lausanne a admis la requête de mesures préprovisionnelles. Cette décision n'a pas été respectée par le père, lequel s'est prévalu de l'arrêt de la Cour d'appel de Gand du 2 avril 2012. C.c. Par ordonnance du 16 août 2012, le Juge de paix du district de Lausanne a fait droit à une nouvelle requête de mesures préprovisionnelles de la mère et a suspendu le droit de visite du père jusqu'à la tenue de l'audience du 2 octobre 2012. C.d. À l'audience du Juge de paix du district de Lausanne du 14 novembre 2012, les parties ont passé une convention s'agissant de l'exercice du droit de visite pour les vacances de Noël et de février, à savoir que A._ aurait sa fille auprès de lui du samedi 29 décembre 2012 à 12.00 heures au samedi 5 janvier 2013 en fin d'après-midi et du lundi 18 février 2013 à 12.00 heures au samedi 23 février en fin d'après-midi, à charge pour B._ d'amener, à ses frais, l'enfant chez son père qui, à ses frais la ramènera chez sa mère. Cette convention a été homologuée par le Juge de paix pour valoir ordonnance de mesures provisionnelles. C.e. Le 15 novembre 2012, le Juge de paix a chargé le Service de protection de la jeunesse d'une enquête. L'enfant des parties a été entendue par la Justice de paix le 28 novembre 2012. D. Le 2 novembre 2012, A._ a saisi la Chambre des tutelles du Tribunal cantonal du canton de Vaud d'une demande de reconnaissance et d'exequatur de l'arrêt de la Cour d'appel de Gand du 2 avril 2012. Par jugement du 4 décembre 2012, la Chambre des tutelles a rejeté cette demande et mis les frais et les dépens à la charge du requérant. E. Le 30 janvier 2013, A._ exerce un recours en matière civile contre ce jugement concluant à la reconnaissance et à l'exequatur de l'arrêt de la Cour d'appel de Gand du 2 avril 2012. À l'appui de ses conclusions, il invoque un abus de droit de la mère et conteste qu'une reconnaissance de l'arrêt belge puisse heurter l'ordre public suisse. Il se plaint également de ce que des frais et des dépens ont été mis à sa charge. Invitées à se déterminer sur le recours, la cour cantonale s'est référée aux considérants de son arrêt tandis que l'intimée a conclu à son irrecevabilité, subsidiairement à son rejet par mémoire du 19 avril 2013. F. Le 27 juin 2013, le Tribunal fédéral a délibéré sur le recours en séance publique.