Faits :
A.
A.a. C._ est née en 2014 à X._ (GE) de la relation entretenue par B._ (1976), de nationalité russe, et A._ (1972), de nationalité belge.
C._ a été reconnue par son père devant l'officier d'état civil.
B._ a un fils, né en 2006 de son mariage avec D._, désormais dissous.
A.b. Le 5 mai 2015, B._ et A._ ont signé une déclaration concernant l'autorité parentale conjointe, laquelle a été ratifiée par le Tribunal de protection de l'adulte et de l'enfant (ci-après: le Tribunal de protection) le 18 mai 2015.
B.
B.a. Le 12 décembre 2016, B._ a formé devant le Tribunal de protection une requête en constatation de l'autorité parentale exclusive de la mère non mariée, assortie d'une requête de mesures superprovisionnelles et provisionnelles.
A ce dernier titre, B._ a conclu à ce que tout contact entre C._ et A._ fût interdit pour une durée indéterminée, mais dans tous les cas jusqu'à la fin de la procédure pénale ouverte à l'encontre de E._, ami de A._, pour actes d'ordre sexuel avec des enfants, à ce qu'il fût fait interdiction à A._, dans tous les cas, de sortir du territoire suisse avec l'enfant C._, à ce qu'il fût constaté que l'autorité parentale exclusive (y compris le droit de garde exclusif), était détenue par la mère et au besoin à ce que cette autorité parentale exclusive lui fût attribuée.
Sur le fond, B._ a conclu à ce que la déclaration concernant l'autorité parentale conjointe du 5 mai 2015 fût invalidée pour vice de forme, à ce qu'il fût constaté qu'elle était toujours seule titulaire de l'autorité parentale sur l'enfant C._, à ce qu'un droit de visite fût attribué à A._ avec interdiction de quitter le territoire suisse et à condition qu'il fût libéré de toutes charges à l'issue de la procédure pénale ouverte à l'encontre de E._. Subsidiairement, et si le Tribunal de protection devait considérer qu'elle-même et A._ détenaient tous deux l'autorité parentale conjointe, à ce que celle-ci fût retirée au père pour lui être attribuée exclusivement.
Par ordonnance du 13 décembre 2016 rendue sur mesures superprovisionnelles, le Tribunal de protection a fait interdiction à A._ d'entretenir des contacts avec sa fille, de modifier le lieu de résidence de la mineure et de quitter avec elle le territoire suisse, sans son autorisation préalable. Le dépôt immédiat des documents d'identité de la mineure en possession de son père a été ordonné en mains du Service de protection des mineurs (ci-après: SPMi) et l'autorité parentale sur l'enfant a été retirée au père. La décision a été prise sous la menace de la peine prévue à l'<ref-law> et l'inscription de la mineure au RIPOL a été ordonnée.
B.b. Le 14 décembre 2016, A._ a déposé à son tour une requête de mesures superprovisionnelles et provisionnelles de protection pour la mineure C._, concluant à ce qu'il fût fait interdiction à B._ de déplacer la résidence de l'enfant, à ce que celle-ci fût inscrite dans les registres de police suisses et internationaux, à ce qu'il fût ordonné à la mère de déposer les papiers d'identité de la mineure et à ce que lui-même pût bénéficier d'un droit de visite.
Par ordonnance du 16 décembre 2016, le Tribunal de protection, statuant sur mesures superprovisionnelles, a fait interdiction à B._ de modifier le lieu de résidence de sa fille, de faire quitter la Suisse à l'enfant sans l'autorisation préalable du Tribunal de protection, a ordonné le dépôt immédiat des documents d'identité de la mineure en mains du SPMi, la décision étant rendue sous la menace de la peine prévue à l'<ref-law>, et a ordonné l'inscription de l'enfant au RIPOL.
B.c. Le 19 décembre 2016, le conseil de B._ a informé le Tribunal de protection que celle-ci, accompagnée de sa fille était partie pour Y._ (Russie) le 6 (recte: 16) décembre 2016 à 7h30 du matin, à savoir avant la notification de l'ordonnance rendue le même jour. Sa cliente serait toutefois de retour après les fêtes de fin d'année, à savoir le 8 janvier 2017.
B.d. Le 22 décembre 2016, A._ a sollicité du Tribunal de protection qu'il revienne sur l'interdiction qui lui avait été faite d'entretenir toute relation avec sa fille et sur le retrait de l'autorité parentale. Il indiquait avoir été entendu le 13 décembre 2016 dans le cadre de la procédure pénale diligentée pour actes d'ordre sexuel à l'encontre de E._ et ne pas avoir été mis en prévention. Il contestait également le vice de forme allégué par B._ relatif à la déclaration d'autorité parentale conjointe.
B.e. Le 28 décembre 2016, B._ a formé devant les tribunaux de Y._ une demande tendant à faire constater que le domicile de sa fille se trouvait en Russie; elle a également réclamé le versement d'une contribution d'entretien à A._.
B.f. Le 9 janvier 2017, le conseil de A._ informait le Tribunal de protection que B._ n'était pas rentrée de Russie, contrairement à ce qu'elle avait précédemment affirmé.
Par courrier de son conseil du 12 janvier 2017, B._ a fait part de son intention de rester provisoirement en Russie, déclarant craindre pour sa vie et pour l'intégrité corporelle de ses enfants. Le même jour, un second courrier a été adressé au Tribunal de protection, courrier indiquant que trois experts avaient examiné C._ en Russie. Ceux-ci étaient unanimes quant au fait que l'enfant avait " sans aucun doute " participé à des jeux à caractère sexuel et avait " très probablement " été victime d'attouchements ou autres actes à caractère sexuel.
B.g. Le 25 janvier 2017, A._ s'est déterminé sur la requête de mesures provisionnelles formée par B._ devant le Tribunal de protection. Il a conclu à son rejet et, faisant suite à sa propre requête de mesures provisionnelles, à ce que l'autorité parentale conjointe sur l'enfant fût immédiatement réinstaurée, à ce qu'un droit de visite lui fût réservé, à ce qu'il fût ordonné à B._ de rapatrier immédiatement l'enfant sous la menace de la peine de l'<ref-law> et à ce que l'interdiction faite à l'intéressée de quitter le territoire suisse fût confirmée.
B.h. Par ordonnance du 6 février 2017, le Tribunal de protection, statuant sur mesures provisionnelles, a notamment levé l'interdiction faite à A._ d'entretenir tout contact avec sa fille C._, lui a restitué l'autorité parentale sur l'enfant, lui a réservé un droit aux relations personnelles devant s'exercer à raison de trois contacts téléphoniques par semaine dans l'attente du rapport d'évaluation sociale que le SPMi était invité à établir dans les meilleurs délais.
B.i. Le SPMi a rendu son rapport le 11 mai 2017. Celui-ci relevait le manque de coopération de B._ dans la mise en oeuvre du droit de visite via Skype; il soulignait en revanche la collaboration du père de l'enfant et ses bonnes compétences parentales.
B.j. Une requête de retour fondée sur la CLaH80 a été transmise à l'Autorité centrale russe le 16 mai 2017 par l'intermédiaire de l'Office fédéral de la justice.
La médiation entre les parties a échoué.
B.k. Par ordonnance du 21 novembre 2017, statuant sur mesures provisionnelles, le Tribunal de protection a notamment retiré à B._ la garde de fait et le droit de déterminer le lieu de résidence de C._, ordonné le placement de l'enfant chez son père, ordonné à B._ de ramener la mineure en Suisse et réglé le droit aux relations personnelles entre celles-ci.
B._ a formé recours contre cette ordonnance, sollicitant la restitution de l'effet suspensif.
Par décision du 18 décembre 2017, la Chambre de surveillance de la Cour de justice a attribué l'effet suspensif au recours; le Tribunal fédéral a déclaré irrecevable le recours formé par A._ contre cette décision (arrêt 5A_68/2018 du 23 janvier 2018).
La Chambre de surveillance a annulé l'ordonnance du 21 novembre 2017 par arrêt du 5 décembre 2018, estimant que la compétence pour prendre des mesures tendant à la protection de l'enfant avait été transférée à la Russie.
C.
Agissant le 7 janvier 2019 par la voie du recours en matière civile au Tribunal fédéral, A._ (ci-après: le recourant) conclut à l'annulation de la décision cantonale et à sa réforme en ce sens que préalablement, il soit dit et constaté que les autorités judiciaires suisses sont compétentes pour prendre toutes mesures de protection concernant la mineure C._. A titre principal, le recourant demande que la garde de fait et le droit de déterminer le lieu de résidence de l'enfant soient retirés à B._ (ci-après: l'intimée), que le placement de l'enfant soit ordonné chez lui, qu'il soit ordonné à l'intimée de ramener l'enfant en Suisse et de collaborer avec les curateurs, un droit aux relations personnelles à raison d'un week-end sur deux, d'une journée en semaine et la moitié des vacances scolaires avec interdiction de quitter la Suisse étant réservé à l'intimée, qu'une curatelle d'organisation et de surveillance des relations personnelles entre la mineure et l'intimée soit instaurée, qu'une curatelle d'assistance éducative soit mise en place, le SPMi étant invité dans les plus brefs délais à transmettre le nom des intervenants désignés à ce titre et les mesures prises dans les ordonnances des 13 et 16 décembre 2016 étant maintenues pour le surplus; à titre subsidiaire, le recourant sollicite le renvoi de la cause à l'instance cantonale pour nouvelle décision au sens des considérants.
L'intimée a spontanément produit devant la Cour de céans copie de l'ordonnance rendue le 20 novembre 2018 par la Cour suprême de la Fédération de Russie, décision rejetant le pourvoi en cassation formé par le recourant dans le cadre de sa requête en retour de l'enfant.
Invités à se déterminer, l'intimée a conclu au rejet du recours, la cour cantonale s'est référée aux considérants de son arrêt et le SPMi n'a présenté aucune observation. Les parties n'ont pas déposé d'écritures complémentaires.

Considérant en droit :
1.
La décision entreprise nie la compétence des autorités suisses pour prendre des mesures tendant à la protection de l'enfant mineure des parties, conclusion qui l'a en conséquence conduite à annuler la décision du Tribunal de protection prononçant de telles mesures et à mettre ainsi fin à la procédure initiée par la mère devant cette dernière juridiction. Il s'agit donc d'une décision finale (<ref-law>).
Les autres conditions de recevabilité du recours en matière civile sont réalisées (art. 72 al. 1, 75 al. 1 et 2; 76 al. 1, 100 al. 1 et 46 al. 2 LTF), étant précisé que la cause n'est pas de nature pécuniaire en sorte que l'exigence liée à la valeur litigieuse minimale n'entre pas en considération.
La pièce produite par l'intimée devant la Cour de céans est irrecevable (<ref-law>).
2.
2.1. Dès lors que la décision querellée a été prise dans le contexte d'un prononcé de mesures provisionnelles, seule peut être dénoncée la violation des droits constitutionnels (<ref-law>). Le Tribunal fédéral ne connaît de la violation de ces droits que si un tel moyen est invoqué et motivé par le recourant (principe d'allégation; <ref-law>), c'est-à-dire s'il a été expressément soulevé et exposé de manière claire et détaillée (<ref-ruling> consid. 3.2 et les arrêts cités). Le recourant qui se plaint d'arbitraire ne saurait, dès lors, se borner à critiquer la décision attaquée comme il le ferait en procédure d'appel, où l'autorité de recours jouit d'une libre cognition; il ne peut, en particulier, se contenter d'opposer sa thèse à celle de l'autorité précédente, mais doit démontrer, par une argumentation précise, que cette décision est manifestement insoutenable (<ref-ruling> consid. 3). Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 2.4 les arrêts cités).
2.2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Le recourant qui entend invoquer que les faits ont été établis de façon manifestement inexacte ne peut obtenir la rectification ou le complètement des constatations de fait que s'il démontre la violation de droits constitutionnels, conformément au principe d'allégation susmentionné (cf. supra consid. 2.1). Le recourant ne peut pas se borner à contredire les constatations litigieuses par ses propres allégations ou par l'exposé de sa propre appréciation des preuves; il doit indiquer de façon précise en quoi ces constatations sont arbitraires au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.4.3). Une critique des faits qui ne satisfait pas à cette exigence est irrecevable (<ref-law>; <ref-ruling> consid. 1.3.1; <ref-ruling> consid. 2.3 et les références).
3.
Le recourant se plaint d'abord du retard pris par la cour cantonale pour statuer, alors que la procédure portait sur des mesures provisionnelles. Il y voit une violation du principe de célérité, garanti par les art. 29 Cst. et 6 CEDH, qui doit à son sens conduire à l'annulation de l'arrêt entrepris.
En tant que la cour cantonale a définitivement statué sur le recours dont elle était saisie, le grief n'a toutefois plus d'objet. Le recourant ne peut en effet se prévaloir d'aucun intérêt actuel et pratique à faire constater un éventuel retard à statuer, étant précisé que la nature formelle de la garantie invoquée ne saurait pallier cette absence d'intérêt (<ref-ruling> consid. 4a).
4.
4.1. La cause revêt un caractère international vu les nationalités russe, respectivement belge, des parents de l'enfant, qui, après avoir quitté Genève à la fin de l'année 2016, se trouve désormais en Russie avec sa mère.
4.2. En matière de protection des enfants, l'<ref-law> prévoit que la compétence des autorités judiciaires ou administratives suisses, la loi applicable ainsi que la reconnaissance et l'exécution des décisions ou mesures étrangères sont régies par la CLaH96.
Tant la Suisse que la Russie sont parties à cette convention, en sorte que celle-ci est ici applicable.
5.
5.1. Selon l'art. 5 CLaH96, les autorités, tant judiciaires qu'administratives, de l'État contractant de la résidence habituelle de l'enfant sont compétentes pour prendre des mesures tendant à la protection de sa personne ou de ses biens (al. 1). En cas de changement de la résidence habituelle de l'enfant dans un autre État contractant, sont compétentes les autorités de l'État de la nouvelle résidence habituelle, sous réserve d'un déplacement ou d'un non-retour illicite au sens de l'art. 7 CLaH96 (al. 2). Le principe de la perpetuatio fori ne s'applique donc pas (arrêts 5A_1010/2015 du 23 juin 2016 consid. 4.1; 5A_864/2014 du 30 janvier 2015; 5A_146/2014 du 19 juin 2014 consid. 3.1.1). Il s'ensuit que, dans les relations entre États contractants, le changement (licite) de résidence habituelle du mineur entraîne un changement simultané de la compétence (arrêts 5A_1010/2015 précité ibid.; 5A_324/2014 du 9 octobre 2014 consid. 5.2 et les références). Cela étant, dans l'hypothèse d'un déplacement illicite - défini à l'art. 7 al. 2 CLaH96 dans les mêmes termes qu'à l'art. 3 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] -, l'autorité de l'ancienne résidence habituelle conserve sa compétence pour prendre des mesures jusqu'au moment où l'enfant a acquis une résidence habituelle dans un autre État et que, de surcroît, l'on ne peut plus s'attendre raisonnablement à un retour de l'enfant (arrêt 5A_1010/2015 précité ibid. et la référence), seconde condition que l'art. 7 al. 2 let. b CLaH96 illustre en prévoyant que l'enfant doit ainsi avoir résidé dans l'autre État pour une période d'au moins un an après que la personne ayant le droit de garde a connu ou aurait dû connaître le lieu où il se trouvait, qu'aucune demande de retour présentée pendant cette période n'est encore en cours d'examen et que l'enfant s'est intégré dans son nouveau milieu.
5.2. Le déplacement ou le non-retour de l'enfant est considéré comme illicite au sens de l'art. 7 al. 2 CLaH96 (comme de l'art. 3 CLaH80) lorsqu'il a lieu en violation d'un droit de garde, attribué à une personne, une institution ou tout autre organisme, seul ou conjointement, par le droit de l'État dans lequel l'enfant avait sa résidence habituelle immédiatement avant son déplacement ou son non-retour (let. a), et que ce droit était exercé de façon effective, seul ou conjointement, au moment du déplacement ou du non-retour (let. b).
En matière internationale, le droit de garde comprend le droit portant sur les soins de la personne de l'enfant, et en particulier celui de décider de son lieu de résidence (art. 3 let. b CLaH96; art. 5 let. a CLaH80). Pour déterminer le ou les parent (s) titulaire (s) du droit de garde, il y a lieu de se référer à l'ordre juridique de l'État de la résidence habituelle de l'enfant immédiatement avant le déplacement (arrêt 5A_1010/2015 précité ibid. et les références). Ce moment est également déterminant pour juger de l'illicéité du déplacement (arrêt 5A_1010/2015 précité ibid. et les références). En droit suisse, le droit de déterminer le lieu de résidence de l'enfant est rattaché à l'autorité parentale (<ref-law>; <ref-ruling> consid. 2.3, 502 consid. 2.2, 612 consid. 4.2; <ref-ruling> consid. 4). Le parent qui exerce seul l'autorité parentale peut donc déménager à l'étranger avec l'enfant sans l'accord de l'autre parent (cf. art. 301a al. 2 let. a et ATF <ref-ruling> consid. 4 a contrario), sous réserve toutefois de l'abus de droit (<ref-ruling> consid. 3; arrêts 5A_456/2010 et 460/2010 du 21 février 2011 consid. 3.2; 5A_1010/2015 précité consid. 4.3).
6.
La juridiction cantonale a considéré en substance que l'intimée n'avait pas illicitement déplacé C._ de Suisse, où il n'était pas contesté qu'elle avait jusqu'alors sa résidence habituelle. En tant que, par ordonnance du 13 décembre 2016 rendue sur mesures superprovisionnelles, le Tribunal de protection avait retiré au père l'autorité parentale sur l'enfant, la mère était en effet seule habilitée à déterminer son lieu de résidence. Bien que le père n'eût pas autorisé le déplacement de l'enfant intervenu le 16 décembre 2016, celui-ci n'était en conséquence pas illicite, étant au demeurant précisé qu'il n'était pas établi que la recourante, au moment de son départ, avait déjà reçu notification de l'ordonnance du jour même lui faisant interdiction de déplacer l'enfant hors du territoire suisse. La cour cantonale a par ailleurs relevé que, quelques jours après son arrivée en Russie et alors qu'elle était seule titulaire de l'autorité parentale, la recourante avait effectué des démarches visant à faire constater que le domicile de sa fille se trouvait en Russie, agissant avec l'intention manifeste de s'installer, avec l'enfant, dans son pays d'origine. Dès ce moment, la résidence habituelle de l'enfant se trouvait donc en Russie et non plus en Suisse, en sorte que la compétence pour prendre des mesures tendant à la protection de sa personne ou de ses biens avait été transférée aux autorités russes, conformément à l'art. 5 al. 2 CLaH96.
7.
Le recourant se fonde sur la prémisse que le déplacement de C._ en Russie serait illicite (art. 7 CLaH96), si bien que les autorités genevoises auraient conservé leur compétence. Le déplacement de l'enfant procéderait d'un comportement abusif de la part de sa mère, illustré par plusieurs éléments factuels que l'intéressé reproche à la cour cantonale d'avoir écartés manifestement à tort.
7.1. Le recourant relève d'abord qu'il n'aurait jamais pu être établi que C._ aurait quitté le territoire suisse le 16 décembre 2016 avant que l'intimée eût eu connaissance de l'ordonnance du même jour lui en faisant l'interdiction.
Le fait que l'intimée ait mis plusieurs semaines pour produire des cartes d'embarquement, que leur libellé soit prétendument douteux et que celles-ci ne permettent pas de démontrer la présence de l'enfant dans l'avion relève toutefois de l'appréciation personnelle du recourant, sans aucunement démontrer l'arbitraire de la conclusion cantonale considérant au contraire qu'il n'était pas établi que l'intimée avait déjà reçu notification de l'ordonnance du 16 décembre 2016 au moment de son départ.
7.2. Le fait ensuite que l'intimée aurait contesté devant l'instance de recours la compétence des autorités suisses dès lors qu'elle s'était vu retirer la garde de l'enfant par le Tribunal de protection relève encore de l'appréciation personnelle du recourant; la même conclusion s'impose quant au caractère purement opportun du dépôt, devant les autorités russes le 28 décembre 2016, d'une demande visant à faire constater que le domicile de l'enfant se trouvait en Russie.
7.3. Contrairement ensuite à ce qu'affirme le recourant, il ne ressort pas du procès-verbal d'audience du 22 août 2017 devant le Tribunal de protection, auquel il se réfère, que l'intimée aurait confirmé ne pas avoir annoncé son départ et ne pas contester la compétence des autorités suisses.
7.4. Il s'agit certes de relever, ainsi que le souligne le recourant, que, le 19 décembre 2016, annonçant le départ de sa mandante pour la Russie le 16 décembre 2016, la mandataire de l'intimée a indiqué que ce déplacement n'était que provisoire, l'intéressée devant être de retour en Suisse après les fêtes de fin d'année, à savoir le 8 janvier 2017.
7.4.1. Il faut d'abord souligner, en accord avec la décision entreprise, qu'immédiatement avant la reddition de l'ordonnance du 16 décembre 2016 interdisant à la mère de modifier le lieu de résidence de sa fille, celle-là était seule titulaire de l'autorité parentale, conformément à l'ordonnance rendue à titre superprovisionnel le 13 décembre 2016: l'intimée était ainsi fondée à partir pour la Russie et le déplacement de l'enfant n'était en conséquence pas illicite, le recourant n'étant pas parvenu à démontrer l'arbitraire de la constatation cantonale selon laquelle il n'était pas établi que la mère eût eu connaissance de la décision du 16 décembre avant son départ le même jour.
7.4.2. L'on comprend néanmoins que, par la référence aux déclarations précitées, émises par l'avocate de l'intimée, le recourant tente de démontrer que celle-ci n'aurait décidé de rester en Russie qu'après avoir pris connaissance de l'ordonnance de mesures superprovisionnelles du 16 décembre 2016, circonstance faisant ainsi apparaître illicite le non-retour de l'enfant et permettant en conséquence l'application de l'art. 7 CLaH96. Cette hypothèse n'apparaît toutefois pas plus vraisemblable que celle consistant à retenir, comme l'a implicitement fait la cour cantonale, que, malgré les indications données à son avocate, l'intimée avait, dès son départ, l'intention de ne plus revenir à Genève et de transférer la résidence de l'enfant en Russie. Il n'apparaît en effet pas arbitraire de considérer que la décision de déplacer définitivement l'enfant et de ne pas retourner en Suisse a dû faire l'objet d'une mûre réflexion de la part de l'intimée, antérieure à son départ, plutôt que d'être prise une fois sur place et connue la décision précitée: l'enfant des parties n'a en effet jamais vécu en Russie, l'intimée a elle-même manifestement quitté ce pays depuis plusieurs années et a par ailleurs décidé d'emmener avec elle son fils aîné, issu d'une première union; les démarches officielles en vue de constater la résidence dans ce dernier État ont par ailleurs été effectuées rapidement, à savoir une dizaine de jours après l'arrivée.
7.4.3. L'on précisera de surcroît que la résidence habituelle de C._ en Russie n'a pas fait l'objet de critiques efficaces de la part du recourant. Celui-ci s'est en effet limité à déclarer qu'il la contestait totalement dans le cadre de son argumentation relative à l'art. 7 CLaH96.
7.4.4. En définitive, l'on ne saurait reprocher à la cour cantonale d'avoir arbitrairement écarté sa compétence en référence à l'art. 5 al. 2 CLaH96 en considérant que la résidence habituelle de l'enfant était désormais en Russie où elle avait été licitement déplacée.
7.5. Le recourant fonde pour le surplus son recours sur les conditions d'application de l'art. 7 CLaH96, singulièrement sur l'existence d'une procédure en retour de l'enfant pendante en Russie. Ces critiques sont toutefois vaines en tant que cette dernière disposition n'est pas applicable en l'espèce.
8.
Dans un dernier grief, le recourant invoque la violation de l'art. 8 CEDH, soutenant qu'une décision d'incompétence après une année de procédure et " sur la base d'une décision arbitraire " (sic) consacrerait une violation manifeste des devoirs imposés par cette disposition ainsi que celle du droit au respect de la vie familiale. Cette critique est sans objet, vu l'absence d'arbitraire de la décision querellée constatée au considérant précédent.
9.
En définitive, le recours doit être rejeté dans la mesure de sa recevabilité. Les frais et dépens sont mis à la charge du recourant (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 1'500 fr., sont mis à la charge du recourant.
3.
Une indemnité de 2'000 fr., à verser à l'intimée à titre de dépens, est mise à la charge du recourant.
4.
Le présent arrêt est communiqué aux parties, au Tribunal de protection de l'adulte et de l'enfant du canton de Genève, à la Chambre de surveillance de la Cour de justice du canton de Genève et au curateur de l'enfant C._.
Lausanne, le 1er juillet 2019
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : Herrmann
La Greffière : de Poret Bortolaso