Faits: A. A.a. Ressortissant brésilien né en 1984, A._ a vécu au Portugal, au bénéfice d'un permis de séjour temporaire, valable jusqu'au 30 avril 2011. Il a noué une relation avec D._, une ressortissante portugaise, entrée en Suisse en juillet 2007 et titulaire d'une autorisation de séjour CE/AELE, initialement valable jusqu'au 18 juillet 2012, puis renouvelée. Le **** 2008, D._ a mis au monde à E._ une fille, C._, de nationalité portugaise au bénéfice de la même autorisation de séjour que sa mère. Le 17 juin 2008, A._ a reconnu l'enfant, dont le nom a été modifié en " B._ ". Par convention du 18 septembre 2008, approuvée par la Justice de Paix du district du Pays d'Enhaut le 14 octobre 2008, A._ s'est engagé à payer chaque mois à titre de contributions à l'entretien de l'enfant, allocations familiales non comprises, les sommes de 100 fr. jusqu'à ce que l'enfant ait atteint l'âge de six ans révolus, 150 fr. de six à douze ans révolus, 200 fr. de douze ans à la majorité de l'enfant ou au-delà en cas de poursuites d'études ou d'une formation professionnelle, pour autant qu'elle soit achevée dans des délais normaux. A.b. Le 2 septembre 2009, A._ a sollicité l'octroi d'une autorisation de séjour pour " se rapprocher de sa fille ". Le 12 novembre 2009, le Contrôle des habitants de la commune de F._ a transmis au Service cantonal de la population du canton de Vaud (ci-après: le Service cantonal) une lettre signée de la mère de l'enfant, laquelle indiquait que A._ avait rendu visite à sa fille en avril, juin, octobre et décembre 2008 avant de s'installer en Suisse en juillet 2009. A la demande du Service cantonal, D._ a encore indiqué, le 7 juin 2010, que A._ exerçait son droit de visite en accueillant sa fille chez lui à hauteur de deux jours par semaine et qu'il s'était régulièrement acquitté de la pension alimentaire depuis la naissance de l'enfant. Le 3 août 2010, le Service de la population a informé A._ qu'il avait l'intention de refuser de lui délivrer une autorisation de séjour au motif qu'il séjournait en Suisse de façon illégale, qu'il n'était pas démontré qu'un employeur était prêt à l'engager, ni qu'il disposait des moyens financiers garantissant qu'il ne tomberait pas à l'assistance publique. Dans le délai imparti pour formuler ses objections, A._ a produit quatre lettres d'employeurs disposés à l'engager dans l'hypothèse où il obtiendrait un permis de séjour. A.c. Par décision du 20 octobre 2010, le Service cantonal a refusé de lui délivrer une autorisation de séjour et a prononcé son renvoi de Suisse. La Cour de droit administratif public du Tribunal cantonal de Vaud (ci-après: le Tribunal cantonal) a confirmé cette décision par arrêt du 17 février 2011. Le Tribunal cantonal a retenu que A._ n'avait pas sollicité les autorisations nécessaires à son séjour avec activité lucrative en Suisse et malgré cela s'y était établi et y avait travaillé, de sorte qu'il ne pouvait pas se prévaloir d'un comportement irréprochable. Par ailleurs, n'ayant pas la garde de sa fille, l'intéressé ne pouvait invoquer le bénéfice de l'Accord du 21 juin 1999, entré en vigueur le 1er juin 2002, entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ALCP; RS 0.142.112.681). A.d. Le 31 août 2011, l'Office fédéral des migrations (ci-après: l'Office fédéral) a prononcé une décision d'interdiction d'entrée en Suisse à l'encontre de l'intéressé, valable jusqu'au 30 août 2013. Par ordonnance pénale du 25 octobre 2011, le Procureur de l'arrondissement de l'Est vaudois a condamné A._ à une peine de 40 jours-amende avec sursis durant deux ans et à une amende pour séjour illégal et activité lucrative sans autorisation à raison de faits s'étendant à tout le moins du 6 juin au 11 août 2011. Le 28 mars 2012, la Justice de paix du district de la Riviera-pays-d'Enhaut a approuvé une convention passée à une date inconnue entre les parents, laquelle prévoyait une autorité parentale conjointe ainsi qu'une garde partagée sur leur fille B._. Les parents avaient convenu que A._ garderait B._ du jeudi au samedi, ainsi que la moitié des vacances scolaires et en alternance à Noël et Nouvel-An, Pâques et Pentecôte, l'Ascension et le week-end du Jeûne. La convention prévoyait également que, pour autant que le père trouve un emploi de ferblantier-couvreur, chaque parent prendrait à sa charge les frais d'entretien et de loyer de l'enfant durant le temps où il s'en occupait. Enfin, il était prévu que chaque parent participe à hauteur de 200 fr. par mois aux autres frais (garde, assurance-maladie, vêtements, etc.). Il était précisé que cette convention annulait celle du 18 septembre 2008. B. Le 31 juillet 2012, A._ a sollicité une nouvelle fois une autorisation de séjour pour regroupement familial. A l'appui de sa demande, l'intéressé a produit la convention ratifiée par la Justice de paix, une promesse d'engagement ainsi qu'une assurance d'obtenir un bail pour une chambre. Traitant cette nouvelle requête comme une demande de réexamen, le Service cantonal l'a rejetée par décision du 15 mars 2013. Saisi d'un recours formé par A._ et B._ contre la décision du Service cantonal, le Tribunal cantonal l'a admis par arrêt du 5 juin 2013; il a annulé la décision du 15 mars 2013 et renvoyé le dossier au Service cantonal pour qu'il délivre une autorisation de séjour en faveur de A._. Le Tribunal cantonal a considéré que l'obtention par le père de la garde sur sa fille constituait un fait nouveau justifiant le réexamen et l'octroi d'une autorisation de séjour. C. Agissant par la voie du recours en matière de droit public, l'Office fédéral demande au Tribunal fédéral d'annuler l'arrêt du 5 juin 2013, sous suite de frais et dépens. Les intimés ont conclu au rejet du recours et à l'octroi d'une autorisation de séjour à A._. Le Tribunal cantonal se réfère aux considérants de l'arrêt entrepris. Le Service cantonal a renoncé à se déterminer.