Faits:
A. C._, née le 17 décembre 1997, est l'enfant hors mariage de dame B._ et de A._; mère et fille sont de nationalité polonaise. Depuis la naissance, l'autorité parentale sur l'enfant appartient exclusivement à la mère.
Depuis 2002, les parents entretiennent des relations conflictuelles quant à leur fille; ils ont déposé plusieurs requêtes devant les autorités tutélaires du canton de Genève; une curatelle d'assistance éducative, exercée par le Service de protection des mineurs (ci-après: SPMi), a été mise en place.
B. Par décision du 6 avril 2006, l'Autorité de surveillance des tutelles du canton de Genève a retiré à dame B._ la garde de l'enfant et l'a attribuée au père, réservé à la prénommée un droit de visite à exercer un week-end sur deux et durant la moitié des vacances scolaires, confirmé la curatelle de surveillance des relations personnelles, étendu le mandat du tuteur au choix de l'école et du pédopsychiatre de l'enfant et restreint dans cette mesure l'autorité parentale de la mère. Le 29 septembre 2006, le Tribunal fédéral a rejeté les recours formés par dame B._ contre cette décision.
C. C.a Le 24 décembre 2007, la mère s'est établie officiellement à D._ dans le canton de Berne, où elle avait déjà précédemment vécu.
C.b Le 26 janvier 2008, à la suite d'une fugue, C._, qui était scolarisée depuis le début de l'année à l'Institut E._ à F._ (Vaud), a été accueillie dans le foyer d'urgence X._, situé près de D._.
Saisi la veille d'une requête de mesures de protection urgentes de la mère, l'Autorité tutélaire de D._ a, le 28 janvier suivant, transmis la cause aux autorités tutélaires genevoises; elle a exposé qu'elle n'avait aucune connaissance du dossier relatif à l'enfant concerné et que, vu la nature des mesures à prendre, la complexité de l'affaire et l'intervention préalable des autorités tutélaires genevoises, ces dernières pouvaient prendre rapidement les mesures de protection nécessaires.
C.c Par "clause péril" du 8 février 2008, le SPMi genevois a provisoirement retiré au père le droit de garde et décidé de maintenir le placement de la fillette au foyer X._. Il a considéré que l'enfant avait besoin d'être préservée des incessants conflits parentaux et que seule cette structure pouvait lui offrir la protection requise, ce qui excluait qu'elle le quitte pour passer des vacances avec son père, comme celui-ci en avait manifesté l'intention.
Le 26 février 2008, ce service a rendu un rapport circonstancié faisant état de nombreux incidents survenus au cours de l'année 2007, qui attestaient la persistance du conflit aigu existant entre les parents, lesquels utilisaient leur fille l'un contre l'autre; il a conclu à la ratification de la clause péril ainsi qu'à la confirmation du placement dans le foyer et, au fond, à ce qu'une expertise soit ordonnée pour déterminer le lieu de vie adéquat pour l'enfant et les modalités des relations avec les parents. Le 1er mars 2008, les responsables de l'établissement X._ ont indiqué que la fillette était gravement mise en danger par le conflit de loyauté et les conflits permanents auxquels elle était exposée depuis des années au sein du système familial; ils ont estimé qu'un retour chez l'un ou l'autre des parents n'était pas envisageable.
Par ordonnance du 10 mars 2008, le Tribunal tutélaire a ratifié la décision de clause péril du 8 février précédent, maintenu le placement provisoire dans l'établissement précité jusqu'à nouvelle décision de l'autorité compétente, fixé provisoirement le droit de visite du père et de la mère, à l'exclusion de toute autre personne, à raison de deux heures par semaine chacun, dans le cadre du foyer et s'est, pour le surplus, déclaré incompétent à raison du lieu pour statuer au fond.
C.d Par la suite, les autorités tutélaires genevoise et bernoise ont échangé une correspondance soutenue au sujet de la gestion du dossier.
En particulier, par courrier du 15 juillet 2008, l'Autorité tutélaire de D._ a évoqué ses doutes sur la question de la titularité de l'autorité parentale et qualifié la situation de trop complexe pour une reprise immédiate du dossier; elle a toutefois approuvé les diverses décisions urgentes prises par le Tribunal tutélaire, respectivement par le SPMi, genevois. Le 30 juillet 2008, puis le 14 août suivant, elle a maintenu sa position, considérant qu'au vu de la situation juridique peu claire de l'enfant, le Tribunal tutélaire genevois devait assumer la gestion du dossier. Le 22 août 2008, elle a refusé de donner suite à une requête de placement de l'enfant au foyer X._ que lui adressait le SPMi de Genève.
D. D.a Par décision du 22 août 2008, faisant à nouveau application de la clause péril dans l'attente d'une décision judiciaire du tribunal compétent sur le futur lieu de vie de l'enfant, le SPMi genevois a réitéré le retrait de la garde au père et confirmé le placement au foyer X._ au terme des vacances d'été, ainsi que les modalités du droit de visite précédemment prévues. Le 4 septembre suivant, toujours dans le cadre de la clause péril, il a modifié le lieu de placement en désignant l'internat G._ à D._.
D.b Par ordonnance du 27 octobre 2008, le Tribunal tutélaire du canton de Genève a ratifié la décision de clause péril du 4 septembre 2008 (celle du 22 août qui portait sur une durée limitée, soit jusqu'à la rentrée scolaire, étant devenue sans objet), maintenant ainsi la mesure de retrait du droit de garde et le placement à G._, et réservé aux parents un droit de visite d'une journée par quinzaine chacun de 10 heures à 18 heures ainsi que pendant la moitié des vacances scolaires. Il a en outre invité l'Autorité tutélaire de D._ à accepter en son for les mesures ainsi prises.
D.c Le 3 novembre 2008, le SPMi a informé le tribunal tutélaire d'une détérioration de la situation de la jeune fille, laquelle refusait de rencontrer son père en raison des pressions exercées par celui-ci, des propos inadéquats qu'il lui tenait et de la tension qui en découlait pour elle. Il a également mentionné que le directeur de l'internat avait tenté d'intervenir comme médiateur, mais sans succès, le père cherchant par tous les moyens à entrer en contact avec sa fille. Il a enfin demandé qu'une décision soit prise en vue d'un placement de cette dernière pendant la fermeture de l'établissement scolaire.
Considérant qu'aucun fait nouveau n'était intervenu depuis son ordonnance du 27 octobre précédent, le tribunal a invité le service à recourir contre son prononcé.
D.d Statuant le 4 décembre 2008 sur les recours de A._ et du SPMi, l'Autorité de surveillance du canton de Genève a annulé l'ordonnance du Tribunal tutélaire du 27 octobre précédant. Elle lui a renvoyé la cause pour complément d'instruction et nouvelle décision. Elle a jugé en bref qu'il fallait entendre l'enfant, qui était manifestement prise dans un conflit de loyauté particulièrement aigu et persistant, et organiser sa prise en charge durant les fêtes de fin d'année.
D.e Le 18 décembre 2008, après audition de la fillette, statuant à nouveau sur l'ensemble des points concernés, le Tribunal tutélaire a ratifié la décision de clause péril du 4 septembre précédent et maintenu le retrait du droit de garde du père ainsi que le placement à G._. Il a par ailleurs suspendu provisoirement le droit de visite du père, réservé celui de la mère à raison d'une journée par quinzaine de 10 heures à 18 heures ainsi que pendant les vacances de fin d'année, soit du 5 décembre 2008 au 4 janvier 2009, invité l'Autorité tutélaire de D._ à accepter en son for la mesure de retrait de la garde ainsi que les mesures de curatelle instaurées et déclaré exécutoires nonobstant recours les chiffres du dispositif relatifs au droit de visite des parents.
D.f Sur recours de A._, l'Autorité de surveillance des tutelles a, le 27 février 2009, confirmé cette ordonnance et décidé de la gratuité de la procédure.
En bref, elle a jugé douteuse la recevabilité des conclusions du recourant tendant à une instruction complémentaire, notamment à l'établissement d'une nouvelle expertise psychiatrique. En effet, il apparaissait que le Tribunal tutélaire et partant, elle-même, n'étaient intervenus que pour pallier l'inaction de l'autorité compétente à raison du lieu, quand bien même la compétence de cette dernière était manifeste; il n'était dès lors plus question de retarder encore plus la reprise du dossier par l'Autorité tutélaire de D._.
S'agissant de la garde, l'autorité cantonale a considéré que, depuis de nombreuses années, la fillette était l'otage d'un conflit parental aigu, dont on ne voyait pas l'issue. Ainsi, la solution adoptée le 6 avril 2006 ne s'était pas avérée concluante, le père se montrant incapable de tenir compte de la situation psychologique de sa fille. Si la fugue ne pouvait justifier à elle seule une mesure aussi radicale qu'un retrait de la garde, les différents rapports du foyer X._, où l'enfant avait résidé la première partie de l'année 2008, attestaient de manière indiscutable la nécessité absolue et urgente de protéger la fillette des tensions auxquelles elle était exposée en permanence au contact de ses parents, en particulier de son père. L'enfant, qui se trouvait maintenant en âge de préadolescence et qui avait déjà subi de nombreux bouleversements dans sa vie, devait impérativement pouvoir se concentrer, dans le calme et dans un milieu neutre, sur sa scolarité. L'expertise de famille entreprise en 2005 avait en effet déjà mis en évidence des troubles inquiétants chez cette fillette et il était à craindre que son développement ne soit encore plus gravement mis en danger si la pression familiale devait perdurer.
L'autorité de surveillance a enfin retenu que les relations personnelles entre la mère et la fille n'étaient pas litigieuses. En effet, celle-là avait visiblement réussi à accepter, dans l'intérêt évident de son enfant, de ne voir celle-ci que selon des modalités extrêmement limitées, du moins durant les périodes de scolarité, ce qui devait être considéré comme très positif. Il n'en allait pas de même en ce qui concernait les relations entre le père et sa fille. L'audition de cette dernière par le tribunal tutélaire, de même que les rapports du SPMi, montraient qu'en l'état, même des contacts très espacés et brefs constituaient une source d'angoisse considérable pour la jeune fille qui se sentait mise sous pression et qui souffraient manifestement du fait que les rencontres avec son père ne lui procuraient aucune détente. Dès lors que C._, jusqu'à un passé récent avait su exprimer son attachement à ses deux parents, ce qui montrait que le conflit parental ne l'avait pas empêchée d'entretenir des relations avec l'un ou l'autre, il se justifiait de respecter dorénavant sa demande clairement exprimée de se préserver, en prenant ses distances, de toutes nouvelles contrariétés ou pressions de la part de son père. L'ordonnance entreprise était d'autant moins critiquable que le Tribunal tutélaire avait tout tenté pour préserver un minimum de relations entre le père et sa fille, mais avait dû se rendre à l'évidence que même quelques heures, deux fois par mois, étaient de trop, ce d'autant plus que l'appelant n'était même pas disposé à collaborer avec l'établissement scolaire, malgré les efforts entrepris afin de trouver un modus vivendi acceptable. La situation nécessitait, du moins provisoirement, dans l'intérêt supérieur de l'enfant, la suppression totale du droit de visite du père.
L'autorité cantonale a enfin précisé que, la jeune fille étant scolarisée dans le canton de Berne depuis maintenant plus d'une année, il devenait urgent que l'autorité tutélaire compétente se saisisse du dossier et reprenne l'instruction de la cause, notamment en procédant à l'audition des deux parents, en s'assurant du suivi psychologique de la fillette, en s'enquérant de sa situation scolaire et en examinant si, et selon quelles modalités, des relations personnelles entre l'appelant et sa fille pouvaient être rétablies.
E. Dans une même écriture qu'il intitule "recours constitutionnel et recours civil", A._ exerce un recours au Tribunal fédéral. Il conclut, principalement, à ce qu'il soit réintégré sans délai dans son droit de garde sur son enfant conformément à la décision de l'Autorité de surveillance des tutelles du 6 avril 2006, que sa fille soit inscrite immédiatement à l'école E._, à F._, au lieu de l'école G._, à D._, et à ce que l'intimée et le SPMi soient déboutés de toutes autres conclusions. Il demande, subsidiairement, l'inscription de l'enfant à l'école H._, à Z._, et l'octroi d'un droit de visite aux parents à exercer à raison d'un week-end par quinzaine chacun, de la fin des cours le vendredi à la reprise le lundi matin, ainsi que pendant la moitié des vacances scolaires.
L'autorité cantonale et l'intimée n'ont pas été invitées à répondre.
Considérant en droit:
1. L'arrêt attaqué confirme le prononcé du Tribunal tutélaire du 18 décembre 2008. Celui-ci ratifiait, d'une part, la décision de clause péril du 4 septembre précédent, maintenant le retrait du droit de garde du père ainsi que le placement à l'école G._, suspendant provisoirement le droit de visite du père et réservant à la mère un droit de visite limité. Il invitait, d'autre part, l'Autorité tutélaire de D._ à accepter en son for la mesure de retrait de la garde ainsi que les mesures de curatelle; s'agissant de ce dernier point, il résulte des considérants que cette dernière autorité était pressée de se saisir du dossier et de reprendre l'instruction de la cause, en procédant à l'audition des deux parents, en s'assurant du suivi psychologique de la fillette, en s'enquérant de sa situation scolaire et en examinant si, et selon quelles modalités, des relations personnelles avec le père pouvaient être rétablies.
L'arrêt attaqué combine ainsi une décision sur les mesures de protection de l'enfant (retrait de la garde et placement; suspension provisoire du droit de visite du père) et une décision de transfert du dossier aux autorités tutélaires bernoises comme objet de leur compétence (décision de transfert de for).
Dès lors qu'une telle décision met fin à la procédure devant les autorités tutélaires du canton de Genève, elle est finale (art. 90 LTF; ATF 133 III 629 consid. 2.2 p. 631 et les citations). Elle a par ailleurs été prise en dernière instance par l'Autorité de surveillance des tutelles (art. 75 al. 1 LTF) en matière de protection de l'enfant (art. 72 al. 2 let. b ch. 7 LTF).
Le recours en matière civile étant ouvert, le recours constitutionnel ne l'est pas (art. 113 LTF).
2. Bien que le recourant ne jouisse pas de l'autorité parentale sur sa fille, il a un intérêt juridique à l'annulation ou à la modification de l'arrêt de l'Autorité de surveillance (art. 76 al. 1 let. b LTF); il est en effet directement affecté par la décision attaquée qui lui retire le droit de garde et, corrélativement, place l'enfant dans un internat, et suspend provisoirement son droit de visite (cf. ATF 121 III 1 consid. 2a p. 3; 120 Ia 260 consid. 2a p. 262; arrêt du Tribunal fédéral 5C.51/2005 du 2 septembre 2005 consid. 2.1).
3. La présente procédure a été déclenchée par les clauses péril prises les 22 août et 4 septembre 2008 par le SPMi. Le prononcé rendu dans ce cadre par le Tribunal tutélaire puis, sur recours, par l'Autorité de surveillance, se fondait sur la nécessité de prendre à temps les mesures immédiatement nécessaires à la protection de l'enfant, dont la situation s'était détériorée. Il doit dès lors être considéré comme une décision portant sur des mesures provisionnelles au sens de l'art. 98 LTF (sur cette notion, notamment: ATF 133 III 393 consid. 5 p. 396).
Dans un tel cas, seule peut être dénoncée la violation de droits constitutionnels (art. 98 LTF). 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 (art. 106 al. 2 LTF), c'est-à-dire s'il a été expressément soulevé et exposé de manière claire et détaillée.
4. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF). Dans l'hypothèse d'un recours soumis, comme en l'espèce, à l'art. 98 LTF, le recourant ne peut obtenir la rectification ou le complètement des constatations de fait de l'arrêt cantonal que s'il démontre la violation de droits constitutionnels par l'autorité cantonale. Les art. 95 et 97, ainsi que l'art. 105 al. 2 LTF ne s'appliquent donc pas directement puisqu'ils ne sont pas des droits constitutionnels (ATF 133 III 393 consid. 7.1 p. 398; 133 III 585 consid. 4.1 p. 588). Toutefois, l'application de l'art. 9 Cst. aboutit pratiquement au même résultat: le Tribunal fédéral ne corrige les constatations de fait que si elles sont arbitraires et ont une influence sur le résultat de la décision. Aucun fait nouveau ni preuve nouvelle ne peut être présenté, à moins de résulter de la décision de l'autorité précédente (art. 99 LTF).
Il ne sera ainsi pas tenu compte des faits rapportés sous le chiffre II du recours qui ne ressortent pas de l'arrêt cantonal et dont le recourant ne démontre pas qu'ils auraient été arbitrairement ignorés (cf. supra, consid. 3). Il en va notamment ainsi des allégations selon lesquelles l'intimée aurait organisé la fugue de l'enfant et serait à l'origine de l'attitude négative de cette dernière envers son père. Doivent également être écartées les références - sans pertinence pour l'issue du recours - à l'absence de versement par la mère d'aliments en faveur de sa fille et au non-établissement du passeport de cette dernière en violation d'une décision de justice.
5. Dans le cadre de l'exposé des faits de la cause, le recourant jette le grief d'après lequel le Tribunal tutélaire aurait statué, le "25 juillet 2008", sur le placement de l'enfant à l'internat G._ pour un camp d'été sans audience de comparution personnelle et sans qu'il ait pu produire des écritures. Il reproche aussi à sa Présidente d'avoir, lors de la séance du 15 octobre 2008, violé "des droits fondamentaux de la défense" en refusant d'accepter ses écritures et en l'empêchant de s'exprimer. Ce faisant, il ne dirige pas ses critiques contre l'arrêt attaqué. Celles-là sont dès lors irrecevables.
Il en va de même lorsque le recourant porte des jugements de valeur sur les décisions prises antérieurement, notamment celles des 8 février et 10 mars 2008.
6. Formellement, le recourant conclut principalement à sa réintégration dans son droit de garde "conformément à la décision du 6 avril 2006" et à l'inscription de sa fille à l'école E._. Ce faisant, il demande le rétablissement de la situation qui avait cours avant la fugue de son enfant (droit de garde en sa faveur, sous réserve du droit de visite de la mère à exercer un week-end sur deux et pendant la moitié des vacances scolaires, et scolarité à l'école initialement fréquentée). Son chef de conclusions subsidiaire - qui ne remet pas en cause le retrait de la garde - tend à ce que sa fille soit inscrite dans une école située à mi-chemin entre les domiciles des parents et à l'octroi d'un droit de visite élargi en faveur de ces derniers.
6.1 A l'appui de ces conclusions, le recourant se contente toutefois, sous les intitulés "La clause péril" et "Discussion", de reproduire quasiment mot pour mot des passages de son écriture cantonale. Une telle argumentation ne répond pas aux exigences de motivation de l'art. 42 al. 1 et 2 LTF. Cette disposition impose que le recourant discute au moins de manière succinte les considérants de la décision attaquée, et, lorsque seule peut être invoquée la violation de droits constitutionnels (art. 98 LTF), qu'il invoque un tel grief et le motive conformément aux exigences de l'art. 106 al. 2 LTF (cf. supra consid. 3). Tel n'est pas le cas lorsque la motivation du recours formé devant le Tribunal fédéral est identique à celle qui était déjà présentée dans la procédure cantonale (ATF 134 II 244 consid. 2.1 - 2.3 p. 245 ss).
6.2 Autant qu'on puisse par ailleurs le comprendre du chapitre "IV Au fond", le recourant - qui n'invoque la violation d'aucun droit constitutionnel - critique plus la suspension provisoire de son droit de visite et le choix du lieu de placement que le retrait de son droit de garde proprement dit.
S'agissant de ce dernier point, il se contente de taxer d"affirmation gratuite" "ne repos[ant] sur aucun fait" les considérations de l'autorité cantonale sur son incapacité à prendre en considération la situation psychologique de sa fille et de renvoyer, à titre de preuve, à la "lecture du rapport du service de protection des mineurs du 26 février 2008".
Pour le reste, il reproche à l'autorité cantonale de ne pas avoir statué sur les faits existants au moment où les clauses péril des 22 août et 4 septembre 2008 ont été prises. Il affirme que sa fille et lui-même se rencontraient et se parlaient à cette époque. Le refus de C._ de le voir ne serait intervenu qu'après son placement à l'école G._, auquel il s'était opposé précisément par crainte d'une telle conséquence. Il trouve "consternant" que le SPMi, le Tribunal tutélaire et l'Autorité de surveillance n'envisagent pas que sa fille ait pu être manipulée par sa mère et son entourage, ainsi qu'il a été décrit dans le rapport d'expertise, ni ne remarquent que le changement intervenu à son égard est concomitant au placement dans l'internat précité, dont il relève l'absence de "neutralité".
Autant que le moyen est recevable, on ne saurait suivre le recourant sur ces points. L'Autorité de surveillance n'a pas méconnu qu'il fallait déterminer encore les raisons pour lesquelles l'enfant avait adopté une attitude de refus; elle a admis qu'il devenait "urgent" que l'instruction de la cause soit reprise et qu'il convenait à cet égard de procéder à l'audition des deux parents, de s'assurer du suivi psychologique de la fillette, de s'enquérir de sa situation scolaire et d'examiner, si et selon quelles modalités, des relations personnelles entre les intéressés pouvaient être rétablies. Elle a toutefois renvoyé cette mission aux autorités tutélaires bernoises comme objet de leur compétence (sur ce dernier point: arrêt 5A_607/2008 rendu entre les mêmes parties) - considérations que le recourant ne critique pas - et a statué au vu de l'urgence de la situation sur la base des éléments dont elle disposait en l'état. Pour le surplus, le recourant n'expose pas de façon motivée les motifs pour lesquels l'autorité cantonale ne pouvait pas tenir compte de l'évolution des circonstances depuis l'application des clauses péril ni ne démontre en quoi elle aurait appliqué de façon arbitraire (art. 9 Cst.) l'art. 273 CC, en suspendant provisoirement les relations personnelles père-fille.
7. Vu ce qui précède, le recours doit être rejeté dans la faible mesure de sa recevabilité. Le recourant, qui succombe, supportera les frais de la procédure (art. 66 al. 1 LTF). Il n'y a pas lieu d'allouer de dépens à l'intimée qui n'a pas été invitée à répondre (art. 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 à 2'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué aux parties et à l'Autorité de surveillance des tutelles du canton de Genève.
Lausanne, le 9 septembre 2009
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl Jordan