Faits :
A.
A.a. A.A._, ressortissant macédonien né en 1969, a épousé dans son pays, le 21 février 2005, E._, ressortissante suisse née en 1979. A.A._ est entré en Suisse le 7 novembre 2005 et a obtenu, dans le canton de Berne, une autorisation de séjour régulièrement renouvelée. Le 17 décembre 2010, il s'est vu délivrer une autorisation d'établissement.
A.b. Depuis son arrivée en Suisse, A.A._ a alterné les périodes de chômage et l'exercice d'emplois non qualifiés. Il a bénéficié de l'aide sociale durant plusieurs années pour un montant totalisant 42'918 fr. 80 et a contracté des dettes pour un total de 59'429 fr. 35, dont 51'127 fr. 55 d'actes de défaut de biens. Il a par ailleurs été condamné à deux reprises pour infractions en matière de circulation routière.
A.c. Le 16 août 2011, A.A._ a annoncé son arrivée dans le canton de Neuchâtel au 30 mars 2011. Le 26 août 2011, il a signé avec E._, devant le tribunal compétent, une convention de séparation mentionnant le 1er août 2010 comme date de séparation et autorisant les époux à vivre séparés pour une durée indéterminée. Le jugement de divorce est entré en force le 22 février 2012.
A.d. Par décision du 27 février 2012, le Service des migrations de la République et canton de Neuchâtel (ci-après: le Service cantonal) a refusé de délivrer une autorisation d'établissement à A.A._ dans le canton de Neuchâtel, au motif que l'intéressé avait obtenu une autorisation d'établissement dans le canton de Berne en dissimulant aux autorités compétentes que son mariage n'existait plus que formellement. Par décision du 4 juin 2013, le Département de l'économie (actuellement le Département de l'économie et de l'action sociale de la République et canton de Neuchâtel; ci-après: le Département cantonal) a admis le recours interjeté par A.A._ contre cette décision.
B.
B.a. B._ et ses deux enfants, C.A._, née en 2001, et D.A._, né en 2007, tous ressortissants macédoniens, sont entrés en Suisse le 12 mars 2016.
B._ a déposé une demande d'autorisation de séjour de courte durée en vue de son mariage avec A.A._ et celui-ci a demandé le regroupement familial en faveur de sa future épouse et des deux enfants. Le couple s'est marié en Suisse le 20 mai 2016.
B.b. A.A._ est le père de C.A._. Les parents ont expliqué avoir entretenu une relation à partir de l'année 2000. Ils s'étaient séparés au cours de l'année 2002, à la suite de pressions familiales, et n'avaient repris leur relation qu'au mois de mars 2016. A.A._ avait, ensuite de leur séparation, toujours entretenu des relations avec leur fille ainsi que contribué à son entretien.
A.A._ a reconnu la paternité de D.A._ le 25 avril 2016. Il a tout d'abord soutenu ne pas être le père biologique de cet enfant et l'avoir reconnu dans le but de lui permettre de venir en Suisse. Un rapport d'expertise en lien de parenté établi le 21 mars 2017 a confirmé la probabilité de cette paternité comme étant supérieure à 99.999 %. A.A._ et B._ ont alors expliqué que cet enfant avait été conçu accidentellement lors d'un séjour du premier en Macédoine. Ils avaient toutefois ignoré que A.A._ était le père de D.A._, sa mère ayant à l'époque également fréquenté un autre homme.
B.c. Par décision du 8 juin 2017, le Service cantonal a révoqué l'autorisation d'établissement de A.A._ et classé les demandes de regroupement familial déposées par ce dernier en faveur de son épouse et de leurs deux enfants. Le Département cantonal a rejeté le recours interjeté par les intéressés contre cette décision par prononcé du 29 mars 2018. Par arrêt du 22 novembre 2018, le Tribunal cantonal de la république et canton de Neuchâtel, Cour de droit public (ci-après: le Tribunal cantonal) a rejeté le recours dirigé contre ce prononcé.
C.
Agissant par la voie du recours en matière de droit public, A.A._ (ci-après: le recourant 1), B.A._ (ci-après: la recourante 2), C.A._ (ci-après: la recourante 3) et D.A._ (ci-après: le recourant 4) demandent en substance au Tribunal fédéral, outre le bénéfice de l'assistance judiciaire et l'octroi de l'effet suspensif à leur recours, l'annulation de la révocation de l'autorisation d'établissement du recourant 1 et la délivrance d'autorisations de séjour en faveur des recourants 2, 3 et 4, subsidiairement le renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des considérants.
Le Président de la Cour de céans a admis la requête d'effet suspensif. Le Tribunal fédéral a par ailleurs renoncé provisoirement à demander une avance de frais aux recourants et informé ces derniers qu'il serait statué ultérieurement sur leur demande d'assistance judiciaire.
Le Tribunal cantonal, le Département cantonal et le Service cantonal ont conclu au rejet du recours.
Considérant en droit :
1.
1.1. Selon l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Il est recevable contre les décisions révoquant une autorisation d'établissement - en l'espèce celle du recourant 1 -, car il existe en principe un droit au maintien d'une telle autorisation (ATF 135 II 1 consid. 1.2.1 p. 4). Le sort des prétentions des recourants 2, 3 et 4, lesquels concluent à l'octroi d'autorisations de séjour, dépend de l'issue du recours relatif à la révocation de l'autorisation d'établissement du recourant 1. Il n'est ainsi pas exclu que la recourante 2 et ses enfants puissent se prévaloir d'un droit potentiel à une autorisation de séjour au titre du regroupement familial (cf. art. 43 de la loi fédérale du 16 décembre 2005 sur les étrangers [LEtr; RS 142.20], intitulée, depuis le 1er janvier 2019, loi fédérale sur les étrangers et l'intégration [LEI, RO 2017 6521]; cf. arrêts 2C_112/2019 du 26 février 2020 consid. 1.2; 2C_536/2013 du 30 décembre 2013 consid. 1, non publié in ATF 140 II 129). La présente cause ne tombe ainsi pas sous le coup de l'art. 83 let. c ch. 2 LTF, ni d'aucune autre clause d'irrecevabilité figurant à l'art. 83 LTF. Partant, la voie du recours en matière de droit public est ouverte.
La question de la révocation de l'autorisation d'établissement du recourant 1 sera traitée en premier lieu. Si celle-ci se révèle conforme au droit, les prétentions des recourants 2, 3 et 4 apparaîtront dénuées de fondement (cf. arrêt 2C_299/2012 du 6 août 2012 consid. 1.2 et 4.6).
1.2. Déposé en temps utile (art. 46 al. 1 let. c et 100 al. 1 LTF) et dans les formes prescrites par la loi (art. 42 LTF), par les destinataires de l'arrêt attaqué qui ont un intérêt digne de protection à son annulation ou à sa modification (art. 89 al. 1 LTF), le présent recours, dirigé contre une décision finale (art. 90 LTF) rendue par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 let. d et al. 2 LTF) dans une cause de droit public (art. 82 let. a LTF), est recevable.
2.
2.1. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), sous réserve des cas prévus à l'art. 105 al. 2 LTF (ATF 142 I 155 consid. 4.4.3 p. 156). Le recourant ne peut critiquer les constatations de fait ressortant de la décision attaquée que si celles-ci ont été effectuées en violation du droit au sens de l'art. 95 LTF ou de manière manifestement inexacte, c'est-à-dire arbitraire, et si la correction du vice est susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF; ATF 142 II 355 consid. 6 p. 358). Conformément à l'art. 106 al. 2 LTF, le recourant doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. Les faits invoqués de manière appellatoire sont irrecevables (ATF 141 IV 369 consid. 6.3 p. 375).
2.2. Le Tribunal cantonal a confirmé la révocation de l'autorisation d'établissement du recourant 1 en application de l'ancien art. 63 al. 1 LEtr en lien avec l'ancien art. 62 al. 1 let. a LEtr (qui restent applicables en l'espèce, cf. art. 126 al. 1 LEI), soit pour dissimulation de faits essentiels durant les procédures d'octroi et de prolongation de son autorisation de séjour, puis d'octroi de son autorisation d'établissement. L'autorité précédente reproche sous cet angle au recourant 1 d'avoir tu aux autorités compétentes en matière de droit des étrangers le fait qu'il n'avait pas l'intention de véritablement fonder une communauté conjugale avec sa première épouse, ainsi que d'avoir dissimulé l'existence d'une vie familiale en Macédoine parallèle à son mariage. Les recourants font quant à eux valoir que le Tribunal cantonal aurait procédé à une constatation manifestement arbitraire des faits. Dans la mesure où ce grief se confond en l'espèce avec celui tiré de la violation de l'art. 63 al. 1 let. a LEtr en lien avec l'art. 62 al. 1 let. a LEtr, il sera traité dans ce contexte, de même que le grief d'arbitraire dans l'appréciation anticipée des preuves et celui de la violation du droit d'être entendu qui est lié (cf. infra consid. 4).
2.3. Pour le reste, dans la mesure où les intéressés présentent une argumentation partiellement appellatoire, en complétant ou en modifiant librement l'état de fait retenu dans l'arrêt entrepris, sans exposer en quoi les conditions qui viennent d'être rappelées seraient réunies, le Tribunal fédéral ne peut pas en tenir compte. Il statuera donc sur la base des faits tels qu'ils ont été constatés dans l'arrêt attaqué.
3.
Le litige porte, en premier lieu, sur le point de savoir si c'est à bon droit que le Tribunal cantonal a confirmé la révocation de l'autorisation d'établissement du recourant 1.
4.
Les recourants contestent la réalisation du motif de révocation de l'art. 62 al. 1 let. a LEtr, retenu par les autorités de première instance et confirmé par le Tribunal cantonal.
4.1. D'après l'art. 63 al. 1 let. a et 2 LEtr en relation avec l'art. 62 al. 1 let. a LEtr auquel il renvoie, l'autorité compétente peut révoquer une autorisation d'établissement d'un étranger qui, comme en l'espèce, séjourne en Suisse depuis moins de quinze ans, lorsque ce dernier ou son représentant légal a fait de fausses déclarations ou a dissimulé des faits essentiels durant la procédure d'autorisation. Ainsi, lorsque l'autorité pose des questions à l'étranger, celui-ci doit y répondre conformément à la vérité. Les fausses déclarations qui portent sur des éléments déterminants pour l'octroi de l'autorisation de séjour ou d'établissement conduisent à la révocation de celle-ci. Il ne doit toutefois pas être établi que l'autorisation aurait avec certitude été refusée si l'autorité avait obtenu une information correcte. Quant à la dissimulation de faits essentiels, il faut, au même titre que pour les fausses déclarations, que l'étranger ait la volonté de tromper l'autorité. Cela est notamment le cas lorsqu'il cherche à provoquer, respectivement à maintenir, une fausse apparence sur un fait essentiel (ATF 142 II 265 consid. 3.1 p. 266 et les arrêts cités). L'étranger est tenu de collaborer à la constatation des faits et en particulier de fournir des indications exactes et complètes sur les éléments déterminants pour la réglementation du séjour (cf. art. 90 let. a LEtr); il doit en particulier indiquer si la communauté conjugale sur laquelle son droit de séjour repose n'est plus effectivement vécue (cf. arrêts 2C_261/2018 du 7 novembre 2018 consid. 4.1; 2C_176/2018 du 11 septembre 2018 consid. 3.1; 2C_148/2015 du 21 août 2015 consid. 5.1; 2C_726/2011 du 20 août 2012 consid. 3.1.1; 2C_299/2012 du 6 août 2012 consid. 4.1; 2C_15/2011 du 31 mai 2011 consid. 4.2.1). L'étranger fait preuve d'un comportement trompeur s'il a, dans la procédure d'octroi d'autorisation d'établissement, sciemment tu ou activement caché que, pendant la période de cinq ans déterminante pour l'acquisition de cette autorisation, l'union matrimoniale était vouée à l'échec. La jurisprudence relative à l'invocation abusive de l'union matrimoniale est, ici, pertinente même si elle n'a qu'une portée indirecte (ATF 135 II 1 consid. 4.2 p. 9; arrêt 2C_726/2011 du 20 août 2012 consid. 3.1.2). Selon cette jurisprudence, est considérée comme abusive l'invocation d'un mariage qui n'a plus de substance et n'existe plus que formellement parce que l'union conjugale apparaît définitivement rompue, faute de chances de réconciliation entre les époux (cf. ATF 130 II 113 consid. 4.2 p. 117; 128 II 145 consid. 2 et 3 p. 151 s.). Il en va de même de l'invocation d'un mariage dénué de substance dès ses débuts, soit lorsque celui-ci est contracté dans le seul but d'éluder les dispositions de la loi fédérale sur les étrangers (mariage fictif ou de complaisance), en ce sens que les époux (voire seulement l'un d'eux) n'ont jamais eu la volonté de former une véritable communauté conjugale (cf. ATF 127 II 49 consid. 4a p. 55 et 5a p. 57; arrêts 2C_900/2017 du 7 mai 2018 consid. 8.2; 2C_1055/2015 du 16 juin 2016 consid. 2.2). L'intention réelle des époux est un élément intime (interne) qui, par la nature des choses, ne peut guère être établie par une preuve directe, mais seulement grâce à un faisceau d'indices (cf. ATF 130 II 113 consid. 10.2 p. 135; ATF 127 II 49 consid. 4a p. 55 et 5a p. 57; arrêts 2C_112/2019 du 26 février 2020 consid. 4.1; 2C_403/2018 du 19 février 2019 consid. 3). L'autorité se fonde en principe sur un faisceau d'indices autonomes, aucun des critères n'étant souvent à lui seul déterminant pour juger du caractère fictif du mariage (cf. arrêts 2C_916/2019 du 7 février 2020 consid. 6.2.2; 2C_176/2019 du 31 juillet 2019 consid. 8.2; 2C_900/2017 du 7 mai 2018 consid. 8.2). De tels indices peuvent résulter d'événements extérieurs tels un renvoi de Suisse imminent, l'absence de vie commune, une différence d'âge importante, des difficultés de communication, des connaissances lacunaires au sujet de l'époux et de sa famille ou le versement d'une indemnité (arrêt 2C_112/2019 du 26 février 2020 consid. 4.1). En présence d'indices sérieux d'un mariage fictif, il appartient à l'intéressé de démontrer, par une argumentation circonstanciée, l'existence d'une relation conjugale réellement vécue et voulue (cf. arrêts 2C_900/2017 du 7 mai 2018 consid. 8.2; 2C_1060/2015 du 1er septembre 2016 consid. 5.2; 2C_177/2013 du 6 juin 2013 consid. 3.4). Les indices constituent des constatations de fait que le Tribunal fédéral ne revoit que si elles ont été établies de manière manifestement inexacte ou en violation du droit (art. 97 LTF; ATF 128 II 145 consid. 2.3 p. 152; arrêts 2C_112/2019 du 26 février 2020 consid. 4.1; 2C_631/2018 du 4 avril 2019 consid. 2.2; cf. également supra consid. 2.1).
4.2. En l'espèce, l'instance précédente a déduit de la chronologie des faits et des éléments suivants que le recourant 1 n'avait jamais eu la volonté de créer une véritable relation conjugale avec sa première épouse, mais qu'il avait contracté son premier mariage dans le seul but de s'assurer l'obtention d'un titre de séjour en Suisse. Elle a tout d'abord relevé le soupçon de perception par la première épouse du recourant 1 d'un montant de 30'000 fr. ensuite de leur mariage et de la délivrance d'une autorisation de séjour en faveur de celui-ci, fait relaté par la mère de l'épouse aux autorités fribourgeoises; le déménagement de la première épouse courant 2005 dans le canton de Berne; l'octroi d'une autorisation de séjour au recourant 1 dans ce canton; le courrier du 28 novembre 2005 des autorités fribourgeoises compétentes en matière de droit des étrangers informant le recourant 1 du fait qu'elles envisageaient de lui refuser l'entrée en Suisse dans le cadre du regroupement familial; la transmission de ce courrier aux autorités bernoises et malgré cela le renouvellement régulier de l'autorisation de séjour, puis l'octroi d'une autorisation d'établissement au recourant 1 le 17 décembre 2010. Le Tribunal cantonal a aussi relevé l'annonce, le 16 août 2011, de l'arrivée du recourant 1 dans le canton de Neuchâtel au 30 mars 2011; la mention, dans la convention de séparation du 26 août 2011, du fait que le recourant 1 et sa première épouse n'avaient plus fait ménage commun à partir du 1er août 2010; la vie commune à tout le moins distendue du recourant 1 et de sa première épouse entre le 1er août 2010 et le 30 mars 2011 - date du départ du recourant 1 du domicile conjugal; l'enchaînement rapide entre la délivrance de l'autorisation d'établissement le 17 décembre 2010, le départ du recourant 1 du domicile conjugal le 30 mars 2011 et l'entrée en force du jugement de divorce (22 février 2012) et l'absence d'explication au sujet de cette succession rapide des événements. Puis, le Tribunal cantonal a souligné l'existence d'une relation antérieure à ce premier mariage entre le recourant 1 et la recourante 2; la naissance d'une enfant issue de cette relation en 2001; la reconnaissance, par le recourant 1, le 25 avril 2016, de sa paternité à l'égard du recourant 4, né en 2007, soit pendant le premier mariage; le mariage, le 20 mai 2016, du recourant 1 et de la recourante 2; les premières déclarations du recourant 1 indiquant avoir reconnu le recourant 4 bien qu'il n'en soit pas le père biologique; le rapport d'expertise en lien de parenté du 21 mars 2017 concluant que la probabilité de paternité du recourant 1 envers le recourant 4 est de 99,999 %; les déclarations des parents consécutives aux résultats de cette expertise, expliquant que le recourant 4 avait été conçu de manière accidentelle; les séjours du recourant 1 durant son premier mariage en Macédoine, auprès de sa fille et de la mère de cette dernière ainsi que l'absence d'intérêts et/ou de projets communs du recourant 1 et de sa première épouse. Le Tribunal cantonal a estimé que l'enchaînement de ces événements était révélateur d'une relation étroite entre le recourant 1 et la recourante 2 maintenue parallèlement au premier mariage de celui-ci. Il a considéré que les explications du recourant 1 et de la recourante 2 selon lesquelles ils auraient ignoré la paternité du recourant 1 envers le recourant 4 n'étaient pas crédibles, ni non plus celles exposant que leurs échanges durant le premier mariage du recourant 1 se seraient cantonnés à leur fille.
4.3. Les recourants invoquent une violation de leur droit d'être entendu, en faisant valoir qu'ils ont requis l'audition de la première épouse du recourant 1, de la recourante 2, de la recourante 3 et du recourant 4, et que celles-ci leur ont été refusées. Ce refus aurait en particulier conduit l'autorité précédente à retenir de manière arbitraire que le recourant 1 avait eu une relation parallèle avec la recourante 2 pendant son premier mariage.
4.3.1. Le droit d'être entendu garanti par l'art. 29 al. 2 Cst. comprend notamment le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, d'avoir accès au dossier, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (ATF 142 III 48 consid. 4.1.1 p. 52 s.; 140 I 285 consid. 6.3.1 p. 299 et les références). L'autorité peut cependant renoncer à procéder à des mesures d'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient l'amener à modifier son opinion (ATF 140 I 285 consid. 6.3.1 p. 299 et les références).
4.3.2. En l'occurrence, les recourants méconnaissent que les garanties minimales en matière de droit d'être entendu découlant de l'art. 29 al. 2 Cst. ne comprennent en principe pas le droit d'être entendu oralement (ATF 140 I 68 consid. 9.6.1 p. 76 et les références). Le droit cantonal peut certes, selon les cas, offrir une protection plus étendue aux justiciables (cf. ATF 135 I 91 consid. 2.4.2.1 p. 95 s. a contrario; arrêts 2C_803/2019 du 26 février 2020 consid. 2.2.; 2C_747/2019 du 19 novembre 2019 consid. 3.2). Les recourants ne font toutefois pas valoir que cela serait le cas en l'espèce.
Il ressort en outre de l'arrêt attaqué qu'au terme d'une appréciation anticipée des preuves, le Tribunal cantonal a considéré que les auditions sollicitées n'étaient pas de nature à modifier son opinion. La juridiction précédente a en effet en substance retenu que le recourant 1 et la recourante 2 avaient pu s'exprimer par leurs écritures et les documents déposés et ainsi pu exposer leur situation, que cela soit personnellement ou par l'intermédiaire de leur mandataire. La première épouse du recourant 1 avait également eu l'opportunité de s'exprimer lors des procédures relatives aux autorisations de séjour, puis d'établissement, de celui-ci. En outre, le Tribunal cantonal a estimé que le dossier était suffisamment complet pour l'éclairer sur les éléments essentiels de la cause. Cette appréciation (anticipée) des preuves n'est pas insoutenable. Il est vrai que l'autorité précédente n'a pas mentionné, dans sa motivation, la recourante 3 et le recourant 4. Il ressort toutefois implicitement de l'arrêt attaqué que ceux-ci, tous deux mineurs, ont été représentés par leurs parents respectivement leur mandataire et ont ainsi pu s'exprimer par leur truchement. Il sied en outre de relever que la valeur de preuves des auditions aurait été de toute façon réduite compte tenu de l'intérêt de la recourante 2 et de ses enfants à l'établissement de l'inexistence d'une relation entre elle et le recourant 1 parallèle au premier mariage de ce dernier et l'intérêt de la première épouse du recourant à l'établissement de l'inexistence d'un mariage fictif. C'est partant sans violer le droit d'être entendu que le Tribunal cantonal a renoncé aux auditions sollicitées.
4.4. Par ailleurs, la constatation de l'autorité précédente retenant l'existence d'une relation parallèle entre la recourante 2 et le recourant 1 pendant la durée du premier mariage de celui-ci ne peut que s'imposer au vu de l'ensemble des indices (cf. supra consid. 4.2). On soulignera en particulier l'existence d'une relation entre le recourant 1 et la recourante 2 avant le premier mariage du premier, la naissance de la recourante 3, issue de cette relation; la naissance, durant le premier mariage du recourant 1, d'un autre enfant issu de cette relation, la reconnaissance, par le recourant 1, de la paternité du recourant 4, les quelque quatre mois écoulés entre la délivrance de l'autorisation d'établissement et le départ du recourant 1 du domicile conjugal, ainsi que le mariage subséquent du recourant 1 et de la recourante 2. Cette constatation - qui, contrairement à ce que soutiennent les recourants, ne repose nullement sur la seule contribution du recourant 1 à l'entretien de sa fille - échappe par conséquent au grief d'arbitraire formulé par les recourants et lie le Tribunal fédéral.
4.5. Quant à la déduction du Tribunal cantonal selon laquelle le recourant 1 a contracté son premier mariage sans volonté de fonder une communauté conjugale avec sa première épouse - mais uniquement dans le but de s'assurer l'obtention d'un titre de séjour -, également contestée par les recourants, elle repose sur de nombreux et sérieux indices (cf. supra consid. 4.2). Il appartenait dans ces conditions au recourant 1 d'alléguer et de démontrer, par une argumentation circonstanciée, l'existence d'une relation conjugale réellement vécue et voulue (cf. supra consid. 4.1). L'intéressé s'en est toutefois abstenu - ce que l'instance précédente a relevé à juste titre. Le recourant 1 s'est en effet borné à exposer les motifs pour lesquels le couple formé avec sa première épouse n'avait pas eu d'enfants ni non plus passé de "nombreuses vacances" à l'étranger. Or, de tels éléments ne sont d'aucun secours - il en irait de même s'ils avaient été confirmés par la première épouse du recourant 1 lors d'une audition. On ne saurait par ailleurs reprocher à l'instance précédente de ne pas avoir accordé un poids prépondérant, par rapport aux autres indices, aux évocations toutes générales selon lesquelles le recourant 1 aurait été amené à entretenir des relations sociales et amicales avec l'entourage de sa première épouse, laquelle l'aurait parfois accompagné en Macédoine pour rendre visite à sa fille. Les recourants se méprennent en outre lorsqu'ils affirment que l'autorité précédente aurait considéré que la vie commune du recourant 1 avec sa première épouse aurait pris fin le 1er août 2010. Le Tribunal cantonal, contrairement à ce qu'ils prétendent, a en effet retenu l'existence de relations distendues entre les époux durant la période allant du 1er août 2010 au 30 mars 2011 - ce qui va dans le sens des allégations des recourants.
4.6. Dans ces conditions, les constatations de fait de l'autorité précédente retenant, d'une part, l'existence d'une relation parallèle entre la recourante 2 et le recourant 1 pendant le premier mariage de celui-ci, et, d'autre part, l'absence de volonté du recourant 1, dès le départ, de fonder une communauté conjugale avec sa première épouse, ne sauraient être considérées comme arbitraires. Le recourant 1 n'a, contrairement à ses obligations, pas spontanément mentionné ces éléments aux autorités compétentes en matière de droit des étrangers, les trompant ainsi sur le caractère réel et stable de son premier mariage - qui lui avait donné le droit d'obtenir une autorisation de séjour puis d'établissement, conformément à l'art. 42 al. 1 et 3 LEtr (cf. ATF 142 II 265 consid. 3.2 p. 267 et les références citées; arrêts 2C_246/2018 du 7 août 2018 consid. 3.3; 2C_234/2017 du 11 septembre 2017 consid. 6.2). On ne saurait partant reprocher au Tribunal cantonal d'avoir considéré que le recourant 1 avait dissimulé des faits essentiels au sens de l'art. 62 al. 1 let. a LEtr.
4.7. En définitive, les juges précédents n'ont pas violé le droit fédéral en retenant que l'autorisation d'établissement du recourant pouvait être révoquée en application de l'art. 63 al. 1 let. a LEtr en lien avec l'art. 62 al. 1 let. a LEtr. Les griefs des recourants sont rejetés.
5.
Invoquant une violation de l'art. 96 LEtr, le recourant 1 conteste la proportionnalité de la révocation de son autorisation d'établissement.
5.1. Dans le cadre de l'examen de la proportionnalité, il y a lieu de prendre en considération la gravité de l'éventuelle faute commise par l'étranger, son degré d'intégration, la durée de son séjour en Suisse et les conséquences d'un renvoi (cf. ATF 139 I 145 consid. 2.4 p. 149). S'agissant en particulier de la durée du séjour d'un étranger en Suisse, le Tribunal fédéral considère que son importance doit en principe être relativisée lorsque la présence dans le pays a été rendue possible par de fausses déclarations faites aux autorités et, partant, par un comportement contraire à l'ordre public suisse (arrêts 2C_1040/2019 du 9 mars 2020 consid. 5.1; 2C_338/2019 du 28 novembre 2019 consid. 5.3.3 et les arrêts cités; 2C_176/2018 du 11 septembre 2018 consid. 5.2). Par ailleurs, lorsque l'étranger a pu s'intégrer à la faveur de titres de séjour obtenus en trompant les autorités, une bonne intégration ne pèse également qu'un faible poids dans la balance des intérêts à effectuer et ne peut en tout cas pas justifier à elle seule la prolongation du séjour en Suisse (cf. arrêts 2C_1040/2019 du 9 mars 2020 consid. 5.1; 2C_754/2018 du 28 janvier 2019 consid. 6.2 et les arrêts cités). Le Tribunal fédéral a jugé récemment qu'une intégration qualifiée d'"excellente" pouvait jouer un rôle dans un cas où ladite intégration résultait non pas de la période passée en Suisse à la faveur d'un titre de séjour frauduleusement obtenu, mais des nombreuses années antérieures durant lesquelles l'étranger avait séjourné et travaillé régulièrement dans le pays (cf. arrêts 2C_1040/2019 du 9 mars 2020 consid. 5.1; 2C_338/2019 du 28 novembre 2019 consid. 5).
5.2. En l'occurrence, la longueur du séjour du recourant 1 en Suisse, soit plus de treize ans au moment où l'arrêt entrepris a été rendu, doit être relativisée, ainsi que l'a relevé à juste titre le Tribunal cantonal, dès lors que sa présence en Suisse n'a été rendue possible que du fait qu'il a dissimulé aux autorités compétentes en matière de droit des étrangers qu'il avait contracté un mariage sans avoir la volonté de fonder une communauté conjugale avec sa première épouse, d'une part, et l'existence d'une relation parallèle à ce mariage avec la mère de ses deux enfants - dont le second est né durant son premier mariage -, d'autre part. Il en va de même s'agissant des éléments positifs en faveur du recourant 1, soit le fait qu'il a cherché à travailler dès son arrivée en Suisse et sa connaissance du français.
A cela s'ajoute que le recourant 1 ne peut se prévaloir, au vu de sa situation financière et professionnelle (il a émargé à l'aide sociale pour un montant de 42'918 fr. 80 et a des dettes totalisant 59'429.35, dont 51'127 fr. 55 d'actes de défaut de biens; il s'est trouvé au chômage à plusieurs reprises), d'une bonne intégration. Le recourant 1 n'a pas non plus démontré avoir développé des liens particulièrement étroits avec le tissu social suisse. Eu égard aux deux condamnations pour infractions routières dont il a fait l'objet, il ne peut en outre se targuer d'un comportement irréprochable. Le recourant 1 a, qui plus est, vécu la majeure partie de sa vie en Macédoine, pays dont son épouse actuelle et ses deux enfants sont également ressortissants. Cela étant, même si le retour du recourant 1 en Macédoine exigera de sa part un certain effort d'adaptation, une réintégration ne paraît pas d'emblée insurmontable, ce d'autant moins qu'il pourra compter sur le soutien de son épouse - et réciproquement. Le recourant 1 n'a en outre aucune charge de famille en Suisse et est encore relativement jeune (environ 49 ans). Dans la mesure où il est allégué que le frère de la recourante 2 constituerait un danger pour elle et/ou sa fille, on ne voit pas ce qui empêcherait la famille de s'installer à distance de celui-ci pour garantir la sécurité de toutes et tous. Enfin, le recourant 1 ni ne soutient, ni ne démontre, que lui et les membres de sa famille connaîtraient de quelconques problèmes de santé ou qu'ils auraient créé avec la Suisse des attaches étroites au point de les rendre étrangers à leur pays d'origine.
5.3. Compte tenu de l'ensemble de ces circonstances, il n'apparaît pas qu'en faisant primer l'intérêt public à éloigner le recourant 1 sur l'intérêt privé de celui-ci à pouvoir vivre en Suisse, le Tribunal cantonal ait violé le droit fédéral. Le grief de violation du principe de la proportionnalité est partant rejeté.
6.
Dès lors que la révocation de l'autorisation d'établissement du recourant 1 se révèle conforme au droit, son épouse et leurs deux enfants ne peuvent déduire aucun droit à un titre de séjour au titre du regroupement familial.
7.
Les considérants qui précèdent conduisent au rejet du recours.
Les recourants ont demandé à être mis au bénéfice de l'assistance judiciaire. La cause paraissant d'emblée dépourvue de chances de succès, cette requête doit être rejetée (art. 64 al. 1 LTF). Les frais seront donc mis à la charge des recourants, qui succombent, solidairement entre eux, mais fixés en tenant compte de leur situation financière précaire (art. 65 al. 2 et 66 al. 1 LTF). Il ne sera pas alloué de dépens (art. 68 al. 1 et 3 LTF).
Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
La demande d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge des recourants, solidairement entre eux.
4.
Le présent arrêt est communiqué au mandataire des recourants, au Service des migrations du canton de Neuchâtel, au Département de l'économie et de l'action sociale de la République et canton de Neuchâtel, au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, et au Secrétariat d'Etat aux migrations.
Lausanne, le 26 mai 2020
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Kleber