Faits:
A. A.a En date du 18 février 2010, A._ s'est adressé à l'Autorité tutélaire du district de Neuchâtel, lui demandant de désigner un curateur aux enfants B.X._, née le 22 novembre 2005, C.X._, né le 25 février 2007, et D.X._, née le 8 juillet 2008, aux fins d'intenter une action en désaveu de paternité au nom des enfants précités et de le faire inscrire comme étant le père de ceux-ci.
A._ exposait que la mère des enfants, dame X._, avait épousé X._ le 24 novembre 2003, mais que le couple n'avait pas ou très peu vécu ensemble. Lui-même avait entretenu une relation adultérine avec l'intéressée, tous deux ayant fait ménage commun durant plusieurs années. A._ affirmait être ainsi le père des trois enfants et soulignait que la mère avait elle-même des doutes quant à la paternité de son mari.
Le 19 février 2010, la Présidente de l'autorité tutélaire a répondu à A._ qu'il n'avait pas la qualité pour agir en désaveu, se montrant surprise que le prénommé ait attendu 2010 pour s'aviser de sa paternité. Ce dernier a précisé que la mère des enfants s'était séparée judiciairement de son mari le 5 novembre 2009 et qu'aucune démarche n'avait été entreprise antérieurement afin d'éviter à dame X._ des problèmes avec la police des étrangers.
Le 25 juin 2010, l'autorité tutélaire a informé A._ qu'elle avait sollicité de l'office des mineurs une enquête sociale afin de déterminer si une procédure en désaveu serait dans l'intérêt des enfants; le rapport établi concluait toutefois que tel n'était absolument pas le cas. L'autorité considérait dès lors qu'elle n'avait pas à désigner de curateur aux enfants pour introduire une procédure qui ne pourrait finalement que leur nuire.
Le 7 juillet 2010, A._ a demandé à l'autorité tutélaire de revoir sa position, subsidiairement de rendre une décision sujette à recours.
Le 19 juillet 2010, la Présidente de ladite autorité a maintenu son point de vue, lui répondant qu'à la lecture de l'<ref-law>, elle ne voyait pas en quoi il aurait qualité pour agir dans une procédure en désaveu, de sorte que, même si une décision était rendue par l'autorité tutélaire, elle ne lui serait pas notifiée et il n'aurait pas non plus qualité pour recourir.
A.b Le 2 août 2010, A._ a déposé un recours devant la Cour des mesures de protection de l'adulte et de l'enfant du Tribunal cantonal du canton de Neuchâtel. Par arrêt du 24 janvier 2011, ladite autorité a jugé le recours mal fondé, dans la mesure de sa recevabilité.
B. Par acte du 24 février 2011, A._ (ci-après le recourant) interjette, contre cette dernière décision, un recours en matière civile au Tribunal fédéral. Il conclut, à titre principal, au renvoi de la cause à l'autorité intimée avec l'instruction impérative d'entrer en matière sur sa demande; à titre subsidiaire, le recourant demande le renvoi de la cause à l'autorité intimée avec l'instruction impérative de nommer un curateur aux trois enfants en lui donnant mandat d'intenter une action en désaveu de paternité et de le faire inscrire comme étant le père de ces enfants.
Il n'a pas été requis d'observations.

Considérant en droit:
1. Le présent recours, interjeté en temps utile (<ref-law>), est dirigé contre une décision finale (<ref-law>), rendue par la dernière autorité cantonale (<ref-law>). L'instauration d'une curatelle de représentation de l'enfant, fondée sur les art. 306 al. 2 et 392 ch. 2 CC aux fins d'intenter une action en désaveu de paternité (<ref-law>) est une décision de nature non pécuniaire en matière de protection de l'enfant, sujette au recours en matière civile (art. 72 al. 2 let. b ch. 7 LTF; arrêt 5A_128/2009 du 22 juin 2009 consid. 1.2 et la référence). En tant que le recourant remet en cause le refus de sa qualité pour recourir en instance cantonale, il dispose de la qualité pour recourir au sens de l'<ref-law> (arrêt 5A_194/2011 du 30 mai 2011 consid. 3.2). Le recours en matière civile est donc en principe recevable.
2. 2.1 Le recours en matière civile peut être formé pour violation du droit fédéral (<ref-law>). Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour d'autres motifs que ceux qui ont été invoqués et le rejeter en adoptant une argumentation différente de celle de l'autorité précédente (cf. <ref-ruling> consid. 1.1). Le Tribunal fédéral ne connaît de la violation des droits constitutionnels que si un tel moyen est invoqué et motivé par le recourant (<ref-law>), c'est-à-dire s'il a été expressément soulevé et exposé de manière claire et détaillée (principe d'allégation; <ref-ruling> consid. 3.2 et les arrêts cités).
2.2 Le Tribunal fédéral ne peut s'écarter des faits établis par l'autorité précédente que si ceux-ci 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>), à savoir arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.4.1 p. 39; <ref-ruling> consid. 1.2.2 p. 252), doit satisfaire au principe d'allégation (supra consid. 2.1). Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 2 p. 591/592 et les arrêts cités).
3. 3.1 L'arrêt de la cour cantonale mêle décisions sur la recevabilité (défaut de qualité pour recourir) et sur le fond (absence d'intérêt des enfants à l'action).
Se fondant sur la jurisprudence parue aux <ref-ruling> (infra consid. 3.4.1), appliquée par analogie à la curatelle de représentation en vue de l'introduction d'une action en désaveu, la juridiction cantonale a retenu que l'autorité tutélaire ne devait pas se préoccuper des intérêts ou des droits du père présumé (recte: naturel) lors de l'institution de dite curatelle. La question de savoir si le père présumé (recte: naturel) était ainsi habilité à interjeter un recours conformément à l'<ref-law> se limitait par conséquent à déterminer s'il défendait les intérêts légitimes des enfants. Observant que le rapport d'enquête sociale établi le 10 juin 2010 concluait que l'intérêt des enfants ne commandait pas l'introduction d'une action en désaveu, les juges cantonaux en ont conclu que, à supposer qu'une décision formelle de l'autorité tutélaire refusant l'institution d'une curatelle eût été rendue, le recourant n'aurait pas eu la qualité pour recourir au sens de l'<ref-law>. Il s'ensuivait qu'il n'avait pas non plus la qualité pour se plaindre d'un déni de justice concernant le refus de rendre une décision sujette à recours.
3.2 Le recourant soutient qu'il était légitimé à requérir la nomination d'un curateur pour les enfants dont il se prétend être le père biologique afin qu'il les représente dans une procédure en désaveu de paternité, à introduire contre leur père légal. Sa motivation est pour le moins confuse. Il mêle en effet les notions de "qualité pour agir" et de "qualité pour recourir", paraissant fonder sa prétendue légitimation sur l'<ref-law>, dans sa teneur jusqu'au 31 décembre 2010, ainsi que sur l'art. 8 CEDH. L'on peine toutefois à saisir s'il cherche à démontrer être légitimé à réclamer l'instauration de la curatelle litigieuse ou s'il tend en réalité à établir sa qualité pour recourir contre la prétendue absence de décision de l'autorité tutélaire de première instance, le reproche du déni de justice formel étant invoqué entre les lignes.
3.3 A supposer que l'intéressé se plaigne de l'absence de décision de l'autorité tutélaire, son recours n'est pas dirigé contre une décision de dernière instance cantonale au sens de l'<ref-law>, de sorte qu'il est irrecevable. Au demeurant, dans la mesure où la cour cantonale a statué sur le fond du litige, en retenant le défaut d'intérêt des enfants à l'institution d'une curatelle et en rejetant le recours de l'intéressé, ce dernier grief est sans objet.
Il convient dès lors d'examiner avant tout la question de la qualité pour recourir du prétendu père contre la décision refusant la nomination d'un curateur (consid. infra 3.4) puis, dans l'affirmative, d'apprécier si la décision cantonale respecte les exigences du droit fédéral à cet égard (consid. infra 3.5).
3.4 Selon l'<ref-law>, un recours peut être adressé à l'autorité de surveillance contre les décisions de l'autorité tutélaire dans les dix jours à partir de leur communication. Le droit des tiers à former recours est toutefois limité.
3.4.1 Cette voie de droit sert en premier lieu à assurer un comportement de l'autorité tutélaire conforme à la loi et à garantir la protection des intérêts de ceux en faveur desquels elle exerce son activité (<ref-ruling> consid. 2a et les références). La qualité pour recourir conformément à l'<ref-law> est ainsi ouverte au tiers dans la mesure où il invoque les intérêts du pupille à protéger ou la violation de droits ou intérêts personnels (<ref-ruling> consid. 3.1; <ref-ruling> consid. 2a et les références; arrêts 5P.385/2006 du 12 mars 2007 consid. 5.1; 5C.242/2005 du 17 janvier 2006 consid. 2.1 et les références). La poursuite d'intérêts personnels n'est toutefois admise que si les droits ou intérêts propres de l'intéressé doivent être pris en considération s'agissant de l'acte litigieux (<ref-ruling> consid. 3.1).
Ainsi, la jurisprudence a considéré que, lors de l'institution d'une curatelle de représentation en vue d'une action en contestation de paternité (<ref-law> en relation avec l'<ref-law>) ou d'une action en désaveu (<ref-law> en relation avec l'<ref-law>), de même que lors de l'institution d'une curatelle de paternité (art. 309 al. 1 et 2 CC), l'autorité tutélaire se préoccupe exclusivement de l'intérêt de l'enfant: elle n'a pas à veiller aux intérêts ou aux droits des tiers, notamment ceux du père putatif, qui ne disposent d'aucun droit subjectif dans la procédure de tutelle. L'institution de ces formes de curatelle a en effet pour seul objectif de permettre à l'enfant de rompre le lien de filiation avec le père qui l'a reconnu (<ref-law>), respectivement avec le père présumé (<ref-law>), et d'établir cette relation juridique avec le père naturel (<ref-ruling> consid. 2b; arrêt 5C.242/2005 précité consid. 2.2). Il s'ensuit que, lorsque l'autorité tutélaire décide d'instituer une curatelle dans le cadre de ces actions liées à l'établissement de la filiation, le père naturel ou le père légal sont habilités à interjeter un recours selon l'<ref-law> dans la seule mesure où ils défendent l'intérêt personnel de l'enfant (<ref-ruling> consid. 2c; arrêt 5C.242/2005 précité consid. 2.3; PHILIPPE MEIER/MARTIN STETTLER, Droit de la filiation, 4e éd. 2009, note ad n. 82; contra: OLIVIER GUILLOD, in Commentaire romand, Code civil, 2010, n. 11 ad <ref-law>, semble estimer, au sujet de l'action en désaveu, que le refus de nommer un curateur à l'enfant ne peut pas être attaqué par le père biologique, son intérêt personnel ne coïncidant pas forcément avec celui de l'enfant; CYRIL HEGNAUER, Berner Kommentar, 4e éd. 1984, n. 75 ad <ref-law>, paraît quant à lui ouvrir le recours au géniteur sans restriction [ce dernier avis est toutefois antérieur à la jurisprudence publiée aux <ref-ruling>]).
3.4.2 Reste à déterminer ce qu'il advient lorsque le prétendu père naturel requiert la désignation d'un curateur aux fins d'intenter l'action en désaveu et que l'autorité tutélaire lui oppose un refus.
Aux termes de l'<ref-law>, l'enfant né pendant le mariage a pour père le mari. Cette présomption de paternité peut être attaquée devant le juge par le mari (<ref-law>), respectivement par l'enfant si la vie commune des époux a pris fin pendant sa minorité (<ref-law>). L'action de l'enfant est intentée contre le mari et la mère (<ref-law>). Pour l'enfant, il s'agit d'un droit strictement personnel, indépendant de celui du mari de sa mère, qu'il peut ainsi exercer seul s'il a la capacité de discernement (<ref-law>); à défaut, l'enfant doit pouvoir agir par le ministère d'un curateur de représentation (<ref-law>), lequel entreprendra le procès en désaveu au nom de l'enfant (<ref-ruling> consid. 1c et les citations; arrêt 5A_128/2009 du 22 juin 2009 consid. 2.3; parmi plusieurs: MEIER/STETTLER, op. cit., n. 79 s.; HEGNAUER, op. cit., n. 69 s. ad <ref-law>; GUILLOD, op. cit., n. 10 s. ad <ref-law>). L'autorité tutélaire appelée à nommer un curateur à l'enfant doit déterminer si l'ouverture d'une action en désaveu est ou non conforme à l'intérêt de celui-ci (<ref-ruling> consid. 2c p. 4 et les citations). Elle devra d'abord examiner s'il existe des indices permettant de sérieusement douter de la paternité du père légalement inscrit (HEGNAUER, op. cit., n. 72 ss ad <ref-law>; Repertorio di giurisprudenza patria [Rep] 1998 179 ss [180]). Dans l'affirmative, elle devra alors procéder à une pesée des intérêts de l'enfant en comparant sa situation avec et sans le désaveu (arrêt 5A_128/2009 précité consid. 2.3 et la référence). Elle doit tenir compte des conséquences d'ordre tant psycho-social que matériel, par exemple la perte du droit à l'entretien et des expectatives successorales (<ref-ruling> consid. 2c p. 5; arrêt 5A_128/2009 précité consid. 2.3; HEGNAUER, op. cit., n. 74); il ne sera ainsi pas dans l'intérêt de l'enfant d'introduire une telle action lorsqu'il est incertain que le mineur puisse avoir un autre père légal, lorsque la contribution d'entretien serait notablement moindre, lorsque la relation étroite entre l'enfant et ses frères et soeurs serait sérieusement perturbée et lorsqu'il n'y a pas lieu d'admettre que l'enfant serait en mesure d'entretenir une relation positive sur le plan socio-psychique avec son géniteur (arrêt 5A_128/2009 précité consid. 2.3 et la référence). En tant qu'il faisait valoir l'intérêt des enfants à l'action en désaveu, le recourant, prétendu père naturel, devait donc se voir reconnaître la qualité pour interjeter recours.
Aux termes de l'<ref-law>, l'enfant né pendant le mariage a pour père le mari. Cette présomption de paternité peut être attaquée devant le juge par le mari (<ref-law>), respectivement par l'enfant si la vie commune des époux a pris fin pendant sa minorité (<ref-law>). L'action de l'enfant est intentée contre le mari et la mère (<ref-law>). Pour l'enfant, il s'agit d'un droit strictement personnel, indépendant de celui du mari de sa mère, qu'il peut ainsi exercer seul s'il a la capacité de discernement (<ref-law>); à défaut, l'enfant doit pouvoir agir par le ministère d'un curateur de représentation (<ref-law>), lequel entreprendra le procès en désaveu au nom de l'enfant (<ref-ruling> consid. 1c et les citations; arrêt 5A_128/2009 du 22 juin 2009 consid. 2.3; parmi plusieurs: MEIER/STETTLER, op. cit., n. 79 s.; HEGNAUER, op. cit., n. 69 s. ad <ref-law>; GUILLOD, op. cit., n. 10 s. ad <ref-law>). L'autorité tutélaire appelée à nommer un curateur à l'enfant doit déterminer si l'ouverture d'une action en désaveu est ou non conforme à l'intérêt de celui-ci (<ref-ruling> consid. 2c p. 4 et les citations). Elle devra d'abord examiner s'il existe des indices permettant de sérieusement douter de la paternité du père légalement inscrit (HEGNAUER, op. cit., n. 72 ss ad <ref-law>; Repertorio di giurisprudenza patria [Rep] 1998 179 ss [180]). Dans l'affirmative, elle devra alors procéder à une pesée des intérêts de l'enfant en comparant sa situation avec et sans le désaveu (arrêt 5A_128/2009 précité consid. 2.3 et la référence). Elle doit tenir compte des conséquences d'ordre tant psycho-social que matériel, par exemple la perte du droit à l'entretien et des expectatives successorales (<ref-ruling> consid. 2c p. 5; arrêt 5A_128/2009 précité consid. 2.3; HEGNAUER, op. cit., n. 74); il ne sera ainsi pas dans l'intérêt de l'enfant d'introduire une telle action lorsqu'il est incertain que le mineur puisse avoir un autre père légal, lorsque la contribution d'entretien serait notablement moindre, lorsque la relation étroite entre l'enfant et ses frères et soeurs serait sérieusement perturbée et lorsqu'il n'y a pas lieu d'admettre que l'enfant serait en mesure d'entretenir une relation positive sur le plan socio-psychique avec son géniteur (arrêt 5A_128/2009 précité consid. 2.3 et la référence). En tant qu'il faisait valoir l'intérêt des enfants à l'action en désaveu, le recourant, prétendu père naturel, devait donc se voir reconnaître la qualité pour interjeter recours.
3.5 3.5.1 Sur le fond, l'autorité de surveillance a indiqué que, selon les informations recueillies par l'autorité tutélaire, l'intérêt des enfants ne commandait pas l'introduction d'une action en désaveu. Pour déterminer cet intérêt, l'autorité cantonale s'est fondée sur un rapport d'enquête sociale, établi par l'office des mineurs le 10 juin 2010, après audition de la mère et entretien téléphonique avec l'ex-mari de cette dernière, père légal des enfants. Il ressort dudit rapport que ceux-ci avaient toujours entretenu une relation affective suivie avec X._ qu'ils considéraient comme leur père; celui-ci restait un soutien pour la famille, malgré le fait qu'il fût séparé de la mère. Le rapport souligne également que les enfants n'avaient plus revu le recourant depuis octobre 2009, qu'ils avaient assisté à des scènes de violence subies par leur mère et qu'ils craignaient de revoir l'intéressé. Ce dernier avait en outre été condamné à une peine privative de liberté de huit mois avec sursis pour lésions corporelles infligées aux membres de la famille de la mère des enfants. Le rapport note également que, dans l'hypothèse où la paternité du recourant devait être établie, l'instauration d'un droit de visite se révélerait impossible, même par le biais d'un point rencontre. Enfin, le recourant avait proféré des menaces par téléphone envers la Présidente de l'autorité tutélaire et le personnel du greffe.
3.5.2 Le recourant se plaint de ne pas avoir pu consulter le rapport d'enquête sociale sur lequel s'est fondée la juridiction cantonale pour conclure à l'absence d'intérêts des enfants à introduire une action en désaveu. Il remarque également que l'enquête aurait été établie unilatéralement en ce sens que seule la mère des enfants, dont les allégations n'étaient pas objectives, aurait été entendue.
A supposer que la critique du recourant réponde aux exigences posées par l'<ref-law> (consid. 2.1 supra), elle ne permet pas de conclure à l'existence d'une violation de son droit d'être entendu.
Dans le domaine de la protection de l'enfance en particulier, domaine dans lequel la maxime d'office s'applique de façon illimitée, l'autorité compétente peut, en vertu de son pouvoir d'appréciation, mener l'enquête de façon inhabituelle et, de son propre chef, se procurer des rapports: c'est en effet le bien de l'enfant qui est déterminant en premier lieu (cf. <ref-law>; <ref-ruling> consid. 4a). En outre, comme dans toutes les affaires personnelles, le droit de participer à l'administration des preuves peut être limité si des raisons le justifient. C'est le juge qui décide, en vertu de son pouvoir d'appréciation et en fonction des intérêts en jeu, dans quelle mesure les parties sont exclues de l'administration des preuves (cf. art. 156 du code de procédure civile fédéral [CPC]). Il suffit alors que les parties aient ultérieurement la possibilité de se prononcer sur le résultat de la preuve pour que leur droit d'être entendu soit garanti (<ref-ruling> consid. 4a et les références; arrêt 5C.210/2000 du 27 octobre 2000 consid. 2a publié in FamPra.ch 2001 p. 606; 5A_860/2009 du 26 mars 2010 consid. 2.2).
En l'espèce, l'enquêteur social s'est en effet fondé sur les seules déclarations de la mère et du père légal des enfants. Le recourant s'est néanmoins fait entendre, sur recours, par l'autorité de surveillance, devant laquelle il a pu produire toute pièce utile. Il s'ensuit que l'on ne saurait constater une violation de son droit d'être entendu.
3.5.3 Le recourant affirme enfin que l'établissement d'un lien de paternité entre lui-même et les enfants serait dans leur intérêt: ceux-ci pourraient prétendre à l'octroi d'une contribution d'entretien qu'il serait prêt à leur verser et leur filiation juridique coïnciderait avec leur lien génétique. La nomination d'un curateur était en outre nécessaire au vu des rapports particuliers qu'il entretenait avec la mère des enfants, celle-ci risquant de ne pas défendre suffisamment et correctement les intérêts de ces derniers. Ce serait enfin en se fondant sur des faits établis arbitrairement que la juridiction cantonale aurait confirmé l'absence d'intérêt des enfants à l'introduction d'une telle action.
Les allégations du recourant sont pour l'essentiel appellatoires, celui-ci se contentant d'opposer sa propre version des faits à celle retenue par l'autorité cantonale sur la base de l'enquête sociale. Il en est ainsi lorsqu'il affirme que le père légal n'aurait jamais eu aucune relation avec les enfants, qu'il ne pourvoirait pas à leur entretien, contrairement à lui-même, qui se serait toujours comporté en père attentif. Quant à la nécessité de nommer un curateur au vu des rapports tendus que le recourant entretient avec la mère des enfants elle ne concerne en rien l'introduction d'une action en désaveu. L'existence de ces tensions, que le recourant assimile lui-même à une "guerre de clans", va d'ailleurs clairement à l'encontre de l'intérêt de ceux-ci à d'une telle procédure.
En définitive, si le recourant prétend invoquer un intérêt des enfants à l'institution d'une curatelle en vue d'une action en désaveu, force est d'admettre qu'il n'est pas à même de l'étayer ou, du moins, de contredire les faits cantonaux permettant de dénier l'existence d'un tel intérêt.
4. Le recours est rejeté, dans la mesure où il est recevable. Les frais judiciaires sont mis à la charge du recourant qui succombe (<ref-law>). L'autorité intimée n'a droit à aucun dépens (<ref-law>); la requête d'assistance judiciaire déposée par la mère des enfants concernés est sans objet, des observations n'ayant pas été sollicitées.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La requête d'assistance judiciaire de dame X._ est sans objet.
3. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué aux parties et à la Cour des mesures de protection de l'enfant et de l'adulte du Tribunal cantonal du canton de Neuchâtel.
Lausanne, le 29 juin 2011
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl de Poret Bortolaso