Faits :
A.
A._, né en 1986, et B._, née en 1988, sont les parents de C._, née hors mariage en 2010.
B._ a pris la décision de quitter A._ peu de temps avant la naissance de l'enfant.
B.
B.a. Entre 2010 et 2013, le Tribunal tutélaire (désormais: le Tribunal de protection de l'adulte et de l'enfant; ci-après: le Tribunal de protection) du canton de Genève a rendu plusieurs ordonnances relatives à l'aménagement des relations personnelles entre le père et sa fille. Une curatelle d'organisation et de surveillance des relations personnelles a par ailleurs été instaurée.
B.b. Dans un courrier du 26 septembre 2013 adressé au Service de protection des mineurs, B._ a indiqué s'être installée avec sa fille à U._ (Afrique du Sud), où elle avait trouvé un emploi. Elle n'avait informé de son départ ni le père, ni la thérapeute de l'enfant.
Le 7 octobre 2013, A._ a saisi le Tribunal de protection d'une requête visant à ce que l'autorité parentale et la garde de l'enfant soient retirées à la mère et lui soient attribuées, un droit de visite usuel étant réservé à la mère.
Par décision du 10 octobre 2013, le Tribunal de protection a déclaré la requête irrecevable, les tribunaux suisses n'étant pas compétents en raison du domicile de l'enfant en Afrique du Sud.
Le 7 janvier 2014, la Chambre de surveillance de la Cour du justice du canton de Genève (ci-après: la Chambre de surveillance) a annulé cette décision, au motif qu'une résidence habituelle de l'enfant à l'étranger ne pouvait pas être retenue sur la seule base des éléments du dossier.
C.
C.a. A une date indéterminée, la mère a annoncé son retour à Genève.
C.b. Par ordonnance du 31 janvier 2014, le Tribunal de protection lui a fait interdiction d'emmener sa fille hors de Suisse, sous la menace de la peine prévue à l'<ref-law>.
C.c. Le Tribunal de protection a convoqué les parties le 14 février 2014. Lors de cette audience, la mère a expliqué qu'elle était partie en Afrique du Sud pour donner suite à une proposition d'emploi. N'ayant pas obtenu de contrat de travail, elle avait finalement décidé de rentrer en Suisse, dans l'intérêt de sa fille. A l'issue de l'audience, elle s'est déclarée prête à une reprise du droit de visite du père.
Par ordonnance du 14 février 2014 rendue sur mesures provisionnelles, le Tribunal de protection a modifié le droit de visite du père et fixé les modalités suivantes: trois visites de 10h00 à 18h00 espacées de quinze jours, suivies de trois visites du samedi 17h00 au dimanche 18h00 espacées de quinze jours, ensuite un weekend sur deux du samedi 10h00 au dimanche 18h00. Il a fait interdiction à la mère d'emmener l'enfant hors de Suisse, a ordonné la mise en place d'un suivi de guidance parentale en faveur des deux parents et les a invités à y participer activement, a maintenu les curatelles existantes et a prononcé la décision sous la menace de la peine prévue à l'<ref-law>. Il a également ordonné une expertise familiale.
La Chambre de surveillance a confirmé cette décision le 20 mai 2014.
C.d. A la suite de nouvelles tensions entre les parties, le Service de protection des mineurs a, par courrier du 5 juin 2014, préconisé à nouveau le passage de l'enfant par le Point rencontre - mesure que les parties avaient pendant un certain temps considérée non nécessaire - et le maintien des curatelles.
Par ordonnance du 26 septembre 2014, le Tribunal de protection a modifié les modalités du droit de visite fixées par l'ordonnance du 14 février 2014, en ce sens que le passage de l'enfant se ferait par le Point rencontre. Il a également ordonné à la mère de remettre à son [recte: au] père la carte d'identité de l'enfant, ainsi que sa carte d'assurance-maladie lors des visites, ces pièces devant être restituées à la mère à l'issue des visites. Il a par ailleurs rappelé à la mère son devoir de favoriser la relation de l'enfant avec son père et aux deux parties leur devoir d'apaiser leur conflit et d'instaurer entre elles le dialogue et la collaboration indispensables pour éviter à leur enfant un conflit de loyauté.
Le recours de la mère contre cette décision a été déclaré irrecevable.
C.e. Le 12 décembre 2014, l'expert psychiatre a rendu son rapport, qui comportait cinquante pages. Selon lui, il était indiqué que la mère conserve en l'état la " garde " de l'enfant. L'expert n'a toutefois pas exclu que la " garde " soit retirée à la mère en cas d'absence d'évolution positive de la situation. Par ailleurs, il a recommandé, pour les deux parties, un suivi de guidance parentale auprès d'un pédopsychiatre, avec des séances de thérapie mère/fille et père/fille, ainsi qu'une curatelle d'assistance éducative, a préconisé un suivi par un éducateur AEMO afin de permettre la présence d'un tiers à domicile pouvant aider les parents sur le plan éducatif et dans l'identification des besoins de leur fille et a jugé utile d'instaurer une curatelle de soins médicaux pour l'enfant, ainsi qu'un suivi psychothérapeutique individuel pour les deux parents et leur fille. La facture relative à la mission d'expertise se montait à 9'000 fr.
C.f. Le 16 janvier 2015, le Service de protection des mineurs a relevé que le droit de visite du père se déroulait régulièrement, à l'exception d'une visite annulée par la mère. Il préconisait de confirmer le droit de visite tel que défini sur mesures provisionnelles dans l'ordonnance du 14 février 2014, de maintenir le passage de l'enfant par le Point rencontre et la " curatelle de droit de visite ", d'ordonner une curatelle d'assistance éducative ainsi qu'une guidance parentale.
Dans un courrier du 24 février 2015, le Service de protection des mineurs a indiqué avoir rencontré, à leur demande, les parents de la mineure. L'échange s'était révélé constructif, les parties semblant avoir pris conscience de l'impact négatif de leur conflit sur leur fille.
C.g. Lors d'une audience tenue le 26 février 2015 devant le Tribunal de protection, l'expert a pris acte de l'amélioration de la situation, mais a toutefois maintenu ses propositions, les deux parties, tout en étant " sur le bon chemin ", ayant besoin d'être soutenues.
La mère s'est déclarée prête à collaborer avec le Service de protection des mineurs et à accepter l'instauration d'un droit de regard et d'information, ainsi que d'une guidance parentale. Le père a également donné son accord à une telle mesure, et a accepté de " mettre de côté " sa conclusion visant à ce que l'autorité parentale et la garde de l'enfant soient retirées à la mère.
D.
Par ordonnance du même jour, le Tribunal de protection a maintenu les modalités d'exercice des relations personnelles entre le père et sa fille fixées dans les ordonnances des 14 février et 26 septembre 2014 (1), invité le Service de protection des mineurs à préaviser en temps opportun une évolution des modalités d'exercice des relations personnelles, notamment la levée du passage au Point rencontre (2), ordonné la mise en place d'une guidance parentale incluant des séances mère/fille et père/fille auprès d'un pédopsychiatre (3), ordonné la mise en place d'un suivi pédopsychiatrique en faveur de la mineure (4), invité le père et la mère à envisager la mise en place et le suivi régulier d'une thérapie individuelle (5), maintenu la curatelle d'organisation et de surveillance des relations personnelles (6), instauré une mesure de droit de regard et d'information (7) et étendu le mandat des curateurs en conséquence (8), levé l'interdiction de sortie du territoire de la mère avec la mineure prononcée le 14 février 2014 (9), suspendu l'instruction de la cause s'agissant du retrait de l'autorité parentale et de la garde à la mère (10), arrêté les frais judiciaires à 9'000 fr., à charge des parties chacune pour moitié (11).
Statuant sur recours des deux parties, la Chambre de surveillance a, par décision du 13 octobre 2015, annulé le chiffre 5 de l'ordonnance querellée en tant qu'il concernait la mère, et confirmé pour le surplus la décision attaquée.
E.
Par acte du 13 novembre 2015, le père exerce un recours constitutionnel subsidiaire au Tribunal fédéral. Il conclut à l'annulation et à la réforme de la décision de la Chambre de surveillance, en ce sens que les frais judiciaires de la cause fixés " sous chiffre 11 de la décision du Tribunal de protection de l'enfant du 26 février 2015, confirmée par la décision de la Chambre de surveillance de la Cour de justice de la République de l'Etat de Genève datée du 13 octobre 2015 [...] et auxquels [il] a été condamné " soient mis à la charge de B._, ainsi qu'à la condamnation de l'Etat de Genève "en tous les frais et dépens de l'instance ". Il requiert également le bénéfice de l'assistance judiciaire.
Des observations n'ont pas été requises.

Considérant en droit :
1.
1.1. Le recours a pour objet la répartition des frais d'expertise, c'est-à-dire des frais judiciaires (art. 31 al. 1 let. d LaCC/GE cum art. 95 al. 2 let. c CPC; arrêt 4A_438/2014 du 5 novembre 2014 consid. 1.2). Le recours contre une question accessoire, dont fait partie la répartition des frais judiciaires, est soumis à la même voie de droit que celle qui est ouverte contre la décision sur le fond du litige, dans la mesure où aucune procédure spéciale n'est prévue (<ref-ruling> consid. 2.2 p. 95; <ref-ruling> consid. 3 p. 144; <ref-ruling> consid. 1.1 p. 160). En l'espèce, le litige relève sur le fond de la protection de l'enfant, à savoir d'une matière connexe au droit civil (art. 72 al. 2 let. b. ch. 6 LTF).
1.2. La décision querellée confirme l'arrêt du premier juge concernant non seulement les modalités d'exercice des relations personnelles entre le recourant et sa fille, ainsi que l'instauration ou le maintien de diverses mesures d'accompagnement, mais aussi la suspension de l'instruction de la cause s'agissant du retrait de l'autorité parentale et de la garde à la mère. Elle ne met ainsi pas entièrement fin à la procédure et n'est donc pas, à cet égard, une décision finale (<ref-law>; sur la notion de décision finale, cf. <ref-ruling> consid. 2.2 p. 397; <ref-ruling> consid. 1.1 p. 428 et les références). Bien que la question de l'aménagement des relations personnelles et celle de l'autorité parentale et de la garde soient en principe liées (cf. <ref-law>), la cour cantonale les a, en l'espèce, traitées indépendamment l'une de l'autre. En effet, la question de l'autorité parentale et de la garde n'a pas été examinée préalablement à celle de l'aménagement des relations personnelles avec le parent non gardien, de sorte que la décision attaquée peut être qualifiée de décision partielle au sens de l'<ref-law> (sur la notion de décision partielle, cf. <ref-ruling> consid. 2.2 et 2.4 p. 397 ss; <ref-ruling> consid. 1.2.2 et 1.2.3 p. 217 s.), susceptible de recours immédiat au Tribunal fédéral (<ref-ruling> consid. 1.1 p. 422).
1.3. Bien que seule la question des frais judiciaires demeure litigieuse devant le Tribunal fédéral, la cause devant l'autorité cantonale avait pour objet non seulement ce point, mais aussi la nécessité de soumettre l'enfant à un suivi pédopsychiatrique et la mère à une thérapie individuelle, à savoir des questions de nature non pécuniaire (arrêt 5A_96/2013 du 10 octobre 2013 consid. 1.2 et les références), de sorte que le recours est ouvert sans restriction tenant à la valeur litigieuse (<ref-law> a contrario; arrêts 5A_356/2014 du 14 août 2014 consid. 1.1 non publié in <ref-ruling> [dépens]; 5A_52/2015 du 17 décembre 2015 consid. 1 non destiné à la publication [indemnisation du représentant de l'enfant]). La voie du recours en matière civile est ainsi ouverte à cet égard.
1.4. L'intitulé erroné d'un recours ne nuit pas à son auteur, pour autant que les conditions de recevabilité du recours qui aurait dû être interjeté soient réunies (<ref-ruling> consid. 1.1 p. 370; <ref-ruling> consid. 1.2 p. 382). Cela présuppose que le recours puisse être traité dans son ensemble et que les griefs qu'il contient ne doivent pas être examinés dans deux procédures différentes (cf. ATF <ref-ruling> consid. 1.2 p. 382).
En l'espèce, le recourant reproche à l'autorité cantonale d'avoir violé l'interdiction de l'arbitraire dans l'application du droit cantonal supplétif (cf. infra consid. 4.3.1), grief également recevable dans le recours en matière civile (<ref-law>). Le recours sera ainsi traité comme tel.
1.5. Pour le surplus, le recours a été déposé en temps utile (<ref-law>) et dans les formes prescrites (<ref-law>). Le recourant a pris part à la procédure devant l'autorité précédente et démontre un intérêt digne de protection à la modification de la décision attaquée (<ref-law>). Le recours en matière civile est donc en principe recevable.
2.
2.1. Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>), sans être lié ni par les motifs de l'autorité précédente, ni par les moyens des parties; il peut donc admettre le recours en se fondant sur d'autres arguments que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 4 p. 446, 471 consid. 3 p. 472 s.; <ref-ruling> consid. 1.2 p. 383).
Le Tribunal fédéral ne connaît de la violation des droits fondamentaux que si de tels griefs ont été invoqués et motivés par le recourant ("principe d'allégation", <ref-law>; <ref-ruling> consid. 2.2 p. 232; <ref-ruling> consid. 3.3 p. 310 s.), c'est-à-dire s'ils ont été expressément soulevés et exposés de façon claire et détaillée (<ref-ruling> consid. 2.2 p. 232 et les références).
2.2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il peut néanmoins rectifier ou compléter les constatations de la juridiction cantonale de dernière instance si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>) et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>). Le recourant qui soutient que les faits ont été établis d'une manière manifestement inexacte (<ref-law>), c'est-à-dire que les constatations de fait sont arbitraires au sens de l'art. 9 Cst. (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 1.2.2 p. 252), doit satisfaire au principe d'allégation susmentionné (cf. supra consid. 2.1). Le Tribunal fédéral n'entre pas en matière sur des critiques appellatoires portant sur l'appréciation des preuves ou l'établissement des faits par l'autorité précédente (<ref-ruling> consid. 2.3 p. 266; <ref-ruling> consid. 10.1 p. 445; <ref-ruling> consid. 5.1 p. 356).
3.
Dans la partie " En fait " de son mémoire, le recourant, qui estime que " la décision de la Cour de justice genevoise ne prend en considération les faits pertinents de la cause que de manière largement lacunaire ", se contente d'exposer sa propre version des faits. En tant que ces éléments divergent de ceux constatés dans l'arrêt cantonal et qu'ils ne sont pas critiqués sous l'angle de l'établissement arbitraire des faits ou de l'appréciation arbitraire des preuves, il n'en sera pas tenu compte.
Dans la partie " En droit " de son écriture, le recourant se plaint de ce que l'autorité cantonale aurait " om[is] de prendre en compte la quasi-totalité du contexte de fait ayant donné lieu à cette procédure, sans aucun motif et de manière arbitraire ", puis se contente de substituer, de manière purement appellatoire, ses propres visions et appréciations des faits de la cause à celles retenues par la cour cantonale, sans expliquer de manière détaillée en quoi la juridiction précédente aurait arbitrairement écarté un élément de preuve propre à modifier sa décision, se serait manifestement trompée sur son sens ou sa portée, ou serait parvenue, sur la base des éléments recueillis, à des constatations insoutenables. Insuffisamment motivé (cf. supra consid. 2.2.), le grief est irrecevable.
4.
Le recourant reproche par ailleurs à l'autorité cantonale d'avoir appliqué les art. 106 s. CPC de manière arbitraire en répartissant les frais d'expertise par moitié entre les parties.
4.1. L'autorité cantonale a retenu que l'expertise avait été rendue nécessaire par le comportement adopté par les deux parties, lesquelles avaient, depuis la naissance de leur fille, entretenu des relations conflictuelles et n'étaient pas parvenues, en dépit de l'écoulement du temps, à régler l'organisation du droit de visite, multipliant les procédures, au détriment du bien-être et du développement harmonieux de leur enfant. L'expertise, qui contenait des suggestions s'adressant aux deux parents, avait par conséquent été utile à ceux-ci, ainsi qu'à leur fille, de sorte qu'aucune des parties ne pouvait être considérée comme la partie succombante. S'agissant de la situation financière du recourant, la cour cantonale a retenu qu'il était au chômage, ce qui justifiait qu'il ait été mis au bénéfice de l'assistance judiciaire pour les frais de recours. Il s'agissait toutefois d'une situation provisoire, le recourant n'ayant pas établi qu'il ne serait plus en mesure d'exercer une activité lucrative lui permettant de réaliser des revenus plus importants que les indemnités de chômage perçues. Sur cette base, la juridiction précédente a confirmé la décision du premier juge de mettre les frais à la charge des parties, à concurrence de la moitié chacune.
4.2. En substance, le recourant soutient qu'il ne serait pas à l'origine des relations conflictuelles néfastes à l'enfant, que l'intimée a largement acquiescé à ses conclusions ainsi qu'aux propositions faites par les divers intervenants lors de la procédure, qu'il aurait pour sa part "entièrement obtenu gain de cause sur [ses] conclusions, ou à tout le moins, n'aurait succombé sur aucune [d'entre elles] ", que les démarches qu'il a entreprises auraient été effectuées de bonne foi et auraient notamment permis le retour de l'enfant en Suisse et que, contrairement à l'intimée, il n'aurait pas les moyens de s'acquitter de la somme de 4'500 fr. mise à sa charge. Selon lui, les frais judiciaires devraient être entièrement supportés par l'intimée.
4.3.
4.3.1. Lorsque l'autorité de protection de l'enfant est compétente pour statuer sur le droit de visite (<ref-law>), la procédure est réglée par les <ref-law> (arrêt 5A_459/2015 du 13 août 2015 consid. 4.2.2.1 et la doctrine citée). Aux termes de l'<ref-law>, les dispositions de la procédure devant l'autorité de protection de l'adulte sont applicables par analogie. En tant qu'il ne contient pas de règles particulières, le droit fédéral attribue aux cantons la compétence de régir la procédure dans ce domaine (cf. art. 450f in initio CC). Dans le canton de Genève, les art. 1 à 196 CPC s'appliquent à titre subsidiaire devant le Tribunal de protection de l'adulte (art. 31 al. 1 let. d LaCC/GE, sous réserve des exceptions prévues à l'al. 2). Ces dispositions étant applicables à titre de droit cantonal supplétif, le Tribunal fédéral ne peut intervenir que si l'autorité précédente a versé dans l'arbitraire ou enfreint d'autres droits constitutionnels (<ref-ruling> consid. 2.3 p. 386 s.; <ref-ruling> consid. 2.3 p. 231; arrêt 5A_295/2014 du 14 août 2014 consid. 4.1), et pour autant qu'un tel grief ait été invoqué et régulièrement motivé (<ref-law>; cf. supra consid. 2.1).
Conformément à l'<ref-law>, les frais sont en principe mis à la charge de la partie succombante. Lorsqu'aucune des parties n'obtient entièrement gain de cause, les frais sont répartis selon le sort de la cause (<ref-law>). Le tribunal est toutefois libre de s'écarter de ces règles et de répartir les frais selon sa libre appréciation dans les hypothèses prévues par l'<ref-law>, notamment lorsque le litige relève du droit de la famille (art. 107 al. 1 let. c CPC); il n'est ainsi pas exclu, dans ce type de procédure, que la partie qui obtient gain de cause soit condamnée à supporter des frais (arrêts 5A_398/2015 du 24 novembre 2015 consid. 5.1; 5D_76/2012 du 11 septembre 2012 consid. 4.4). Statuant dans ce cadre selon les règles du droit et de l'équité (<ref-law>), l'autorité cantonale dispose d'un large pouvoir d'appréciation non seulement quant à la manière dont les frais sont répartis, mais également quant aux dérogations à la règle générale de l'<ref-law> (<ref-ruling> consid. 3 p. 360; arrêt 5A_398/2015 du 24 novembre 2015 consid. 5.1 et la référence).
4.4. Sur la base de son interprétation des faits (cf. supra consid. 3), le recourant se contente de proposer sa propre appréciation de la question de la répartition des frais, sans démontrer en quoi l'autorité cantonale aurait, sous l'angle de l'arbitraire, commis un excès ou un abus de son pouvoir d'appréciation en mettant les frais pour moitié à charge de chacune des parties. Sa critique, toute générale, selon laquelle " maintenir la décision querellée [...] reviendrait à considérer qu'un père privé de relations personnelles avec sa fille du fait de l'opposition injustifiée de sa mère ne pourrait intenter des procédures judiciaires sensées protéger ses droits et surtout le bien être (sic) de l'enfant, sans se voir imputer les frais de justice et ce, malgré sa bonne foi " n'est pas propre à démontrer que la décision attaquée conduirait à un résultat arbitraire (cf. sur la notion d'arbitraire, <ref-ruling> consid. 2.1 p. 168; <ref-ruling> consid. 3.2.5 p. 339; <ref-ruling> consid. 4.3 p. 319).
Une telle argumentation ne répond pas aux exigences de motivation déduites de l'<ref-law> (cf. supra consid. 2.1) et conduit à l'irrecevabilité du grief.
5.
En conclusion, le recours est irrecevable. La requête d'assistance judiciaire est également rejetée, les conclusions du recourant étant d'emblée dépourvues de chances de succès (<ref-law>). Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>). Il n'est pas alloué de dépens à l'intimée, qui n'a pas été invitée à se déterminer (art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est irrecevable.
2.
La requête d'assistance judiciaire du recourant est rejetée.
3.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à 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 et à la Chambre de surveillance de la Cour de justice du canton de Genève.
Lausanne, le 5 avril 2016
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : von Werdt
La Greffière : Feinberg