Faits :
A.
Le 12 janvier 2013, A._ circulait sur l'autoroute A2 en direction de Bâle sur un tronçon limité à 80 km/h, à une vitesse de 150 km/h, soit, après déduction de la marge de tolérance, avec un excès de vitesse de 64 km/h.
Par décision du 3 décembre 2013, le Département de l'intérieur du canton de Soleure a retiré le permis de conduire de A._ pour une durée de 24 mois du 3 mars 2014 au 2 mars 2016, retrait confirmé sur recours par le Tribunal administratif du canton de Soleure par décision du 16 février 2015.
Le 17 février 2018, A._ a conduit sous l'influence de l'alcool (0.44 mg/l) et, le 28 avril 2018, il a commis un excès de vitesse de 27 km/h hors localité.
Par courrier du 19 juillet 2018, le service cantonal des automobiles et de la navigation (ci-après: SCAN) a constaté que la décision de retrait de permis de conduire prononcée le 3 décembre 2013 et confirmée le 16 février 2015 n'avait pas été exécutée en raison de changement de domicile. Il a octroyé un délai de trois mois à l'intéressé pour déposer son permis. A défaut, la mesure devait être exécutée du 19 octobre 2018 au 18 octobre 2020.
Par décision du 20 juillet 2018, le SCAN a retiré le permis de conduire à A._ pour une durée de quatre mois pour conduite sous l'influence de l'alcool (0.44 mg/l) et excès de vitesse de 27 km/h hors localité, précisant que la mesure entrerait d'office en vigueur à l'échéance de l'exécution du retrait de 24 mois, soit au plus tard du 19 octobre 2020 jusqu'au 18 février 2021.
Le 13 mars 2019, le Département du développement territorial et de l'environnement (ci-après: DDTE) a, sur recours, confirmé la décision.
B.
A._ a recouru devant la Cour de droit public du Tribunal cantonal de Neuchâtel qui, par décision 31 octobre 2019, a rejeté le recours avec suite de frais et dépens. Laissant la question de la recevabilité ouverte, la cour a souligné que A._ ne pouvait pas se prévaloir de son domicile en Allemagne pour prétendre que la mesure de retrait de permis avait été exécutée, qu'il ne contestait pas que les infractions commises en février et avril 2018 pouvaient être respectivement qualifiées d'infraction grave et moyennement grave et que, dès lors, le retrait de permis prononcé pour une durée de quatre mois n'était pas excessif, ce d'autant plus que le retrait de permis de 24 mois n'avait pas été pris en considération, faute de quoi la durée du retrait eût été supérieure aux quatre mois infligés par le SCAN.
C.
Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral, principalement, d'annuler l'arrêt entrepris et de renoncer à tout retrait de permis; subsidiairement, il conclut à l'annulation de l'arrêt attaqué et au renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des considérants. Il sollicite également l'octroi de l'effet suspensif.
Le Tribunal cantonal a conclu au rejet du recours ainsi que le Département de la justice, de la sécurité et de la culture. Invité à se déterminer, le SCAN a précisé dans sa détermination que la décision du 20 juillet 2018 s'applique aussi sur un territoire étranger tant que le recourant n'a pas procédé à l'échange de son permis de conduire suisse contre un dito étranger, de sorte que la période durant laquelle il n'a pas conduit en Suisse ne saurait valoir exécution du retrait de permis.
Par ordonnance du 29 janvier 2020, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif.

Considérant en droit :
1.
La voie du recours en matière de droit public, au sens des <ref-law>, est en principe ouverte contre une décision prise en dernière instance cantonale (art. 86 al. 1 let. d LTF) au sujet d'une mesure administrative de retrait du permis de conduire (<ref-law>), aucune des exceptions mentionnées à l'<ref-law> n'étant réalisée. Le recourant est particulièrement atteint par la décision attaquée, qui confirme le retrait de son permis de conduire pour une durée de 4 mois; il a un intérêt digne de protection à son annulation. Il a donc qualité pour recourir au sens de l'<ref-law>.
En revanche, comme la cour cantonale l'a indiqué, on peut douter de la recevabilité du recours déposé devant le DDTE - et dès lors aussi de la recevabilité du recours déposé devant le Tribunal de céans - en tant qu'il visait l'exécution de la mesure antérieure de retrait de permis de 24 mois (cf. art. 29 let. c de la loi cantonale sur la procédure et la juridiction administratives [LPJA, RS/NE 152.130]). Cette question peut néanmoins rester indécise dès lors que les griefs y relatifs doivent être rejetés (cf. consid. 2 et 3 ci-dessous).
2.
Dans un grief d'ordre formel qu'il convient d'examiner en premier lieu, le recourant fait valoir un établissement manifestement inexact des faits (art. 97 et 105 LTF).
2.1. Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law> (<ref-ruling> 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'<ref-law> 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 (<ref-law>; <ref-ruling> consid. 6 p. 358). Conformément à l'<ref-law>, le recourant doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. Les faits et les critiques invoqués de manière appellatoire sont irrecevables (ATF 141 I 369 consid. 6.3 p. 375).
2.2. Le recourant reproche d'abord à l'instance précédente d'avoir retenu les déclarations relatives à son domicile, faites à la Police neuchâteloise le 17 février 2018, sans l'aide d'un traducteur alors qu'il est de langue maternelle allemande et que sa compréhension du français est rudimentaire.
Les allégations du recourant ne peuvent être suivies. En effet, il a signé, avant l'audition dont il est question, une déclaration rédigée en allemand, selon laquelle il était en droit de demander l'assistance d'un traducteur, droit qu'il n'a pas voulu exercer. Le procès-verbal de l'audition indique qu'il est au bénéfice d'un séjour touristique UE/AELE ou avec visa. Lors de son audition par la police, le recourant a été en mesure de donner de nombreux détails sur son domicile, ses allées et venues en Suisse et en Allemagne. En particulier, il a confirmé qu'il était parti en Allemagne en 1999 pour revenir en Suisse en 2010, qu'il habitait en Suisse avec son épouse depuis 2013 et, qu'au jour de l'audition, il vivait toujours avec cette dernière au bénéfice d'un permis F. Il a également spécifié payer ses impôts en Suisse depuis 2013. Il a une fois encore confirmé ses dires en précisant qu'il logeait chez sa femme et que ses papiers étaient déposés à Neuchâtel depuis 2013. Il a affirmé que, depuis 2013, il avait monté une entreprise en Suisse et y travaillait seul et avait sa clientèle dans les cantons de Neuchâtel, Berne, Vaud et Fribourg. Il n'y a aucune contradiction dans toutes les déclarations du recourant qu'il a enrichies de détails clairs et précis et dûment confirmées par sa signature. Le recourant ne saurait soudainement se prévaloir d'une mauvaise compréhension de la langue française et de l'absence de traductrice, ce à quoi il a précisément renoncé.
Sur la base de ce qui précède, l'autorité précédente pouvait de façon soutenable retenir que le recourant vivait en Suisse depuis 2013 et que ses déclarations reflètent bien la réalité.
3.
Le recourant se plaint également d'une violation du principe de la bonne foi.
3.1. Aux termes de l'art. 5 al. 3 Cst., les organes de l'État et les particuliers doivent agir de manière conforme aux règles de la bonne foi. Cela implique notamment qu'ils s'abstiennent d'adopter un comportement contradictoire ou abusif (<ref-ruling> consid. 4.2 p. 312). De ce principe général découle notamment le droit fondamental du particulier à la protection de sa bonne foi dans ses relations avec l'État, consacré à l'art. 9 in fine Cst. (<ref-ruling> consid. 8.3.1 p. 53 et les arrêts cités). Le principe de la bonne foi protège le citoyen, à certaines conditions, dans la confiance légitime qu'il met dans les assurances reçues des autorités, notamment lorsqu'il a réglé sa conduite d'après des décisions, des déclarations ou un comportement déterminé de l'administration et qu'il a pris sur cette base des dispositions qu'il ne saurait modifier sans subir de préjudice (<ref-ruling> consid. 2.5.1 p. 73). Le principe de la confiance, découlant de celui de la bonne foi, commande également à l'administration d'adopter un comportement cohérent et dépourvu de contradiction; la jurisprudence y a recours parfois pour corriger les conséquences préjudiciables aux intérêts des administrés qui en découleraient (<ref-ruling> consid. 6 p. 87; <ref-ruling> consid. 3a p. 88).
3.2. Le recourant soutient en premier lieu qu'il aurait exécuté le retrait de permis lors de son séjour en Allemagne car, selon lui, il n'est pas contesté qu'il n'a pas piloté de véhicule durant cette période.
Comme l'a souligné la cour cantonale, on ne peut pas suivre le recourant lorsqu'il prétend avoir été domicilié en Allemagne durant la période considérée et n'avoir jamais conduit de véhicule sur le territoire suisse depuis 2015. En premier lieu, il ressort des déclarations du recourant lui-même, déclarations concordantes et constantes, qu'il est venu en Suisse en 2013 et que, depuis cette date, il partage le même domicile que son épouse, à Neuchâtel, où il a monté sa propre entreprise. Il ne peut donc dans le même temps soutenir avoir été domicilié en Allemagne et avoir ainsi exécuté son retrait de permis, ce d'autant moins que les mesures de retrait de permis doivent figurer dans un registre fédéral de mesures administratives en matière de circulation routière (registre ADMAS selon l'ordonnance fédérale sur ledit registre du 18 octobre 2000 en vigueur jusqu'au 31 décembre 2018, puis le registre OSIAC selon l'ordonnance sur le système d'information relatif à l'admission à la circulation en vigueur depuis le 1er janvier 2019 [OSIAC, RS 741.58]). Or, le recourant ne prétend pas que le retrait de permis de 24 mois y figurait quand bien même il lui était loisible de le consulter en application de l'<ref-law>. Enfin, comme l'a souligné le SCAN, le recourant n'a pas procédé à l'échange de son permis de conduire suisse contre un dito étranger, de sorte que la période durant laquelle il n'aurait pas conduit en Suisse ne saurait valoir exécution du retrait de permis.
3.3. Le recourant soutient également que le SCAN l'aurait induit en erreur en lui restituant son droit de conduire, alors qu'il était en possession de son permis, sans avoir fait mention de la non-exécution du retrait de 24 mois.
Dans sa lettre du 20 juillet 2018, le SCAN a notamment indiqué au recourant que le retrait du permis de conduire de 4 mois devrait être exécuté d'office à l'échéance de la mesure de 24 mois prononcée en date du 16 février 2015 par le Tribunal administratif de Soleure, soit au plus tard du 19 octobre 2020 au 18 février 2021. Aucune information ultérieure n'a été communiquée au recourant à ce propos; il ne pouvait déduire de ce silence qu'il était dispensé d'exécuter le premier retrait, tout particulièrement au regard de l'arrêt de la cour cantonale de Soleure du 16 février 2015. On ne peut pas non plus inférer du silence de l'autorité intimée que celle-ci entendait revenir sur les modalités d'exécution de la première mesure puisqu'elle a précisément rappelé dans sa décision que le second retrait de permis serait effectué d'office à la fin du premier retrait de 24 mois. Cela étant et si le recourant nourrissait néanmoins des doutes sur l'exécution de cette mesure, il lui incombait de se renseigner auprès de son avocat mandaté depuis le 23 février 2018, voire directement auprès de l'autorité intimée (cf. <ref-ruling> consid. 1.3.1 p. 203; arrêt 2C_771/2010 du 22 mars 2011 consid. 5.1). En omettant de s'informer, le recourant n'a pas fait preuve de la diligence commandée par les circonstances, de sorte qu'il ne saurait se prévaloir de sa bonne foi.
Mal fondé ce grief doit être rejeté.
4.
Le recourant invoque également une violation de l'<ref-law> au motif que l'autorité n'aurait pas tenu compte de la distance le séparant de son épouse et de ses enfants pour fixer la durée du retrait de permis.
4.1. Conformément à l'<ref-law>, commet une infraction légère la personne qui, en violant les règles de la circulation, met légèrement en danger la sécurité d'autrui et à laquelle seule une faute bénigne peut être imputée. Commet une infraction moyennement grave la personne qui, en violant les règles de la circulation, crée un danger pour la sécurité d'autrui ou en prend le risque (<ref-law>). Commet une infraction grave la personne qui, en violant gravement les règles de la circulation, crée un danger pour la sécurité d'autrui ou en prend le risque (<ref-law>).
Selon l'<ref-law>, les circonstances doivent être prises en considération pour fixer la durée du retrait du permis d'élève conducteur ou du permis de conduire, notamment l'atteinte à la sécurité routière, la gravité de la faute, les antécédents en tant que conducteur ainsi que la nécessité professionnelle de conduire un véhicule automobile. La durée minimale du retrait ne peut toutefois être réduite.
4.2. En l'espèce, il n'est pas contesté que le recourant a commis une infraction grave ainsi qu'une infraction moyennement grave. En cas de faute grave, la durée du retrait de permis est de 3 mois au minimum (<ref-law>). En cas d'infraction moyennement grave, le permis de conduire est retiré pour un mois au minimum (<ref-law>). Lorsque plusieurs actes réalisent plusieurs motifs de retrait de permis de conduire, les règles du droit pénal sur le concours (<ref-law>) sont applicables par analogie pour fixer la durée du retrait de permis. L'autorité administrative devra ainsi prononcer le retrait pour l'infraction la plus grave et en augmenter la durée dans une mesure adéquate (cf. <ref-ruling> consid. 5b p. 183; arrêt 1C_710/2013 du 7 janvier 2014 consid. 3.2; cf. également BUSSY/RUSCONI/JEANNERET/KUHN/MIZEL/MÜLLER, Code suisse de la circulation routière commenté, 4e éd. 2015, rem. 3.2.3 ad <ref-law>).
En l'occurrence, en cumulant les deux durées minimales de retrait de permis, les autorités n'ont pas abusé de leur pouvoir d'appréciation. Il y a d'autant moins abus du pouvoir d'appréciation que, comme le relève la cour cantonale, si l'antécédent ayant donné lieu au retrait de permis de 24 mois avait été pris en considération, la durée du second retrait eût été bien supérieure aux quatre mois infligés. La présence en Suisse de son épouse et de ses enfants ne conduit pas à une autre appréciation, le recourant pouvant en particulier exercer son droit de visite autrement qu'au moyen de sa voiture, comme il prétend l'avoir fait entre 2015 et 2018.
5.
Il s'ensuit que le recours doit être rejeté, dans la mesure où il est recevable, aux frais du recourant qui succombe (art. 65 et 66 al. 1 LTF). Il n'y a pas lieu d'allouer de dépens aux autorités (<ref-law>).

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 à 3'000 francs, sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au mandataire du recourant, au Service cantonal des automobiles et de la navigation de la République et canton de Neuchâtel, au Département du développement territorial et de l'environnement 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, ainsi qu'à l'Office fédéral des routes.
Lausanne, le 8 octobre 2020
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Chaix
La Greffière : Arn