Faits :
A.
A._, dit A._-B._, est né le 5... 1950 en France.
Il était double national suisse et français jusqu'en 2012, année où il a renoncé à sa nationalité française après être revenu en Suisse en 2011 et y avoir obtenu une carte d'identité, sur laquelle figure son nom "A._". C'est également ce patronyme qui résulte de son acte de naissance français et du registre fédéral Infostar.
B.
B.a. Le 30 juin 2014, A._ a demandé l'autorisation de modifier son nom en A._ B._ (avec ou sans trait d'union) au Chef du Département de la formation et de la sécurité (aujourd'hui de l'économie et de la formation; DEF) du canton du Valais. Il a été débouté le 9 juin 2016.
Le 30 novembre 2016, le Conseil d'État du canton du Valais (ci-après: le Conseil d'État) a rejeté le recours administratif exercé par A._ contre cette dernière décision.
Par arrêt du 11 août 2017, le Tribunal cantonal du canton du Valais a rejeté le recours de droit administratif formé par A._.
B.b. Traitant le recours en matière de droit public déposé par A._ comme un recours en matière civile, le Tribunal fédéral a admis celui-ci le 22 janvier 2018, annulé l'arrêt cantonal et renvoyé la cause au Tribunal cantonal pour instruction et nouvelle décision au sens des considérants (arrêt 5A_730/2017).
Statuant sur renvoi du Tribunal de céans le 2 mai 2018, la cour cantonale a rejeté le recours interjeté par A._.
C.
Agissant le 28 mai 2018 par la voie du recours en matière civile, A._ (ci-après: le recourant) conclut à l'annulation de la décision cantonale et à la modification du registre de l'état civil en ce sens qu'il est renommé A._ B._, subsidiairement A._-B._.
Invités à se déterminer, le Conseil d'État (ci-après: l'intimé) se réfère aux considérants de l'arrêt entrepris et conclut au rejet du recours, dans la mesure de sa recevabilité; le Tribunal cantonal, de même que le Département fédéral de justice et police n'ont pas présenté d'observations.

Considérant en droit :
1.
La décision attaquée est une décision finale (<ref-law>), portant sur un changement de nom. Elle est ainsi sujette au recours en matière civile (<ref-law>; arrêt 5A_730/2017 du 22 janvier 2018 consid. 1 et la référence). De nature non pécuniaire, la décision a par ailleurs été rendue sur recours par le tribunal supérieur du canton (<ref-law>), statuant après un arrêt de renvoi du Tribunal fédéral; le recourant, qui a la qualité pour recourir (<ref-law>), a déposé son recours à temps (<ref-law>).
2.
2.1. En vertu du principe de l'autorité de l'arrêt de renvoi du Tribunal fédéral, l'autorité cantonale à laquelle une affaire est renvoyée est tenue de fonder sa nouvelle décision sur les considérants de droit de cet arrêt; sa cognition est limitée par les motifs de l'arrêt de renvoi (<ref-ruling> consid. 5.2 et les références).
Saisi d'un recours contre la nouvelle décision cantonale, le Tribunal fédéral est aussi lié par son arrêt de renvoi (<ref-ruling> consid. 2a); il ne saurait se fonder sur les motifs qui avaient été écartés ou qu'il n'avait pas eu à examiner, faute pour les parties de les avoir invoqués dans la précédente procédure de recours, alors qu'elles pouvaient - et devaient - le faire. La portée de l'arrêt de renvoi dépend donc du contenu de cet arrêt en relation avec les mémoires de recours et de réponse qui avaient été déposés: le procès civil doit parvenir un jour à sa fin et les parties - aussi bien la partie recourante que la partie intimée - doivent soulever tous les griefs qu'elles souhaitent voir traités de façon que le Tribunal fédéral soit en mesure de rendre une décision finale qui clôt le litige (<ref-ruling> consid. 2; <ref-ruling> consid. 4.2; arrêts 5A_785/2015 du 8 février 2016 consid. 2; 9C_53/2015 du 17 juillet 2015 consid. 2.1 et les références).
2.2. Dans les limites dictées par le principe de l'autorité de l'arrêt de renvoi, le recours en matière civile peut être formé pour violation du droit fédéral (<ref-law>), y compris le droit constitutionnel (<ref-ruling> consid. 2.1; <ref-ruling> consid. 2.4). Le Tribunal fédéral applique le droit d'office (<ref-law>) et apprécie librement la portée juridique des faits; il s'en tient cependant aux questions juridiques que la partie recourante soulève dans la motivation du recours et s'abstient de traiter celles qui ne sont plus discutées par les parties, sous réserve d'erreurs manifestes (<ref-law>; <ref-ruling> consid. 2, 115 consid. 2; <ref-ruling> consid. 1.3). Cela étant, eu égard à l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, le recourant doit discuter les motifs de la décision entreprise et indiquer précisément en quoi il estime que l'autorité précédente a méconnu le droit (<ref-law>; <ref-ruling> consid. 2; arrêt 5A_86/2016 du 5 septembre 2016 consid. 1.2).
3.
3.1. En principe, le nom d'une personne est immuable (<ref-ruling> consid. 3.2; <ref-ruling> consid. 3.1; arrêt 5A_730/2017 du 22 janvier 2018 consid. 3.1). Dans certaines constellations propres au droit de la famille (cf. art. 270 al. 2, art. 270a al. 2, art. 8a Tit. fin. CC), la loi autorise le changement de nom de façon inconditionnelle (ch. I de la loi fédérale du 30 septembre 2011 [nom et droit de cité], en vigueur depuis le 1er janvier 2013; RO 2012 2569). S'il existe des motifs légitimes (achtenswerte Gründe, motivi degni di rispetto), le gouvernement du canton de domicile peut également autoriser une personne à changer de nom (<ref-law>, dans sa version en vigueur depuis le 1er janvier 2013). Le point de savoir s'il existe, dans un cas individuel, des " motifs légitimes " en vue du changement de nom relève du pouvoir d'appréciation, que l'autorité compétente doit exercer selon les règles du droit et de l'équité (<ref-law>; <ref-ruling> consid. 3.2).
3.2. Jusqu'à l'entrée en vigueur de l'<ref-law> dans sa nouvelle teneur et l'introduction de la notion de " motifs légitimes ", une personne désirant changer de nom devait faire la démonstration que de " justes motifs " fondaient sa requête, à savoir, outre l'existence de motifs liés au nom lui-même, celle de motifs entraînant des désavantages sociaux concrets et sérieux (cf. de manière générale ATF <ref-ruling> consid. 3.1.1; également MEIER/DE LUZE, Droit des personnes, 2014, n. 289 ss; STEINAUER/FOUNTOULAKIS, Droit des personnes physiques et de la protection de l'adulte, 2014, n. 411 ss). La jurisprudence était particulièrement restrictive à cet égard, ne tenant compte que des motifs objectifs invoqués par le requérant (notamment: arrêts 5C.163/2002 du 1er octobre 2002 consid. 2.1 publié in: FamPra.ch 2003 114; 5C.2/1993 du 14 avril 1993 consid. 3 publié in: REC 61/1993 p. 298 s.; cf. également HAUSHEER/AEBI-MÜLLER, Das Personenrecht des Schweizerischen Zivilgesetzbuches, 4e éd. 2016, n. 16.38; GRAF-GEISER, Das neue Namens- und Bürgerrecht, in: FamPra.ch 2013 251 ss, p. 282).
La modification de l'<ref-law> fait suite aux débats parlementaires en lien avec l'initiative parlementaire 03.428 (Leutenegger Oberholzer), laquelle visait à assurer l'égalité entre époux en matière de nom et de droit de cité. La distinction entre les " motifs légitimes " de la nouvelle disposition et les " justes motifs " de l'ancienne n'a pas fait l'objet de discussions particulières au Parlement (BOCE 2011 479; BOCN 2011 1757; BOCN 2011 1760). Les débats parlementaires démontrent néanmoins que la condition des " motifs légitimes " visait à diminuer les obstacles au changement de nom, sans pour autant ouvrir la possibilité à quiconque de modifier son nom à sa guise (cf. <ref-ruling> consid. 3.3.3 et les références). La modification législative et l'assouplissement qu'elle supposait étaient toutefois essentiellement évoqués en lien avec un changement d'état civil ou des enfants issus de familles recomposées plutôt qu'avec une procédure ordinaire de changement de nom (cf. notamment: BOCN 2011 1757 " mieux prendre en considération les situations personnelles et familiales complexes que l'on rencontre dans notre société actuelle "; BOCN 2011 1760 " damit können vor allem Patchwork-Familien erleichtert wieder zu einem gemeinsamen Namen kommen "). La seule jurisprudence publiée aux ATF depuis la modification législative concerne d'ailleurs le changement de nom d'un enfant autorisé à porter le nom du détenteur de l'autorité parentale après le divorce de ses parents (<ref-ruling>).
Aucun élément ne permet toutefois de restreindre l'assouplissement législatif à un changement d'état civil, voire à un changement de nom réclamé par un enfant en référence à une situation familiale particulière. Selon la jurisprudence, qui suit en cela la doctrine dans sa majorité, la notion de " motifs légitimes " doit ainsi être appréciée de manière plus souple que celle de " justes motifs ", sans se limiter aux domaines sus-évoqués (arrêt 5A_730/2017 du 22 janvier 2018 consid. 3.2; AEBI-MÜLLER, Das neue Familiennamensrecht - eine erste Übersicht, in: RSJ 2012 449, p. 457; STEINAUER/FOUNTOULAKIS, op. cit., n. 411, note infrapaginale 48; BÜHLER, in Basler Kommentar, ZGB I, 5e éd. 2014, n. 5 ad <ref-law>; HAUSHEER/AEBI-MÜLLER, op. cit., n. 16.39; MEIER/DE LUZE, op. cit., n. 288; GUILLOD, Droit des personnes, 5e éd. 2018, n. 54). La requête doit cependant toujours faire état de motifs particuliers (MEIER/DE LUZE, op. cit., n. 292), lesquels ne peuvent être illicites, abusifs ou contraires aux moeurs (arrêt 5A_730/2017 précité consid. 3.2; GEISER, Das neue Namensrecht und die Kindes- und Erwachsenenschutzbehörde, in: RMA 2012 353 ss, n. 3.31; BÜHLER, op. cit., ibid.; GRAF-GEISER, op. cit., p. 283); le nom lui-même doit de surcroît être conforme au droit et ne pas porter atteinte au nom d'un tiers (GEISER, op. cit., n. 3.38). La composante subjective ou émotionnelle de la motivation du requérant ne peut en revanche être écartée comme par le passé, pour autant toutefois que les raisons invoquées atteignent une certaine gravité et ne soient pas purement futiles (arrêt 5A_730/2017 précité consid. 3.2 et les références de jurisprudence cantonale citées; HAUSHEER/AEBI-MÜLLER, op. cit., ibid.; MEIER/DE LUZE, op. cit., n. 292; BÜHLER, op. cit., n. 5 et 9 ad <ref-law>; cf. également GEISER, op. cit., n. 3.31 s.; BÜCHLER, ZGB Kommentar, Schweizerisches Zivilgesetzbuch, 3e éd. 2016, n. 3 ad <ref-law>; plus restrictifs: STEINAUER/FOUNTOULAKIS, op. cit., n. 411). Le nom ne doit en effet pas perdre sa fonction identificatrice et il ne s'agit pas de contourner le principe de son immutabilité, qui reste en vigueur malgré la modification législative.
L'officialisation d'un pseudonyme peut ainsi constituer un motif légitime de changement de nom lorsque les conditions pour qu'il figure sur le passeport à titre de complément officiel (cf. art. 2 al. 4 de la loi fédérale sur les documents d'identité des ressortissants suisses [LDI], RS 143.1) seraient remplies, le requérant devant alors démontrer que son nom d'artiste a une importance objective dans sa vie économique et sociale (à l'aide par exemple de contrats d'artiste, d'articles de presse, d'affiches, de documents sur l'activité artistique, etc.; arrêt 5A_730/2017 précité consid. 3.2; GEISER, op. cit., n. 3.33; restrictifs: STEINAUER/FOUNTOULAKIS, op. cit., n. 414d, qui se réfèrent cependant à la doctrine et la jurisprudence de l'ancien droit).
Un examen attentif des circonstances concrètes reste dans tous les cas nécessaire (<ref-ruling> consid. 3.3.4).
3.3. Lorsque le juge cantonal dispose d'un pouvoir d'appréciation, le Tribunal fédéral ne revoit en principe qu'avec réserve sa décision prise en équité. Il intervient lorsque celle-ci s'écarte sans raison des règles établies par la jurisprudence en matière de libre appréciation, ou lorsqu'elle s'appuie sur des faits qui, dans le cas particulier, ne devaient jouer aucun rôle, ou à l'inverse, lorsqu'elle n'a pas tenu compte d'éléments qui auraient absolument dû être pris en considération; il sanctionnera en outre les décisions rendues en vertu d'un pouvoir d'appréciation lorsqu'elles aboutissent à un résultat manifestement injuste ou à une inéquité choquante (<ref-ruling> consid. 2; <ref-ruling> consid. 5.4).
4.
4.1. Dans son arrêt de renvoi du 22 janvier 2018, la Cour de céans avait admis le grief du recourant relatif à l'établissement arbitraire des faits en tant que le Tribunal cantonal n'avait pas examiné différentes pièces (administratives ou judiciaires pour l'essentiel) produites par l'intéressé et susceptibles d'établir l'éventuelle importance du changement de nom qu'il réclamait dans sa vie sociale et économique.
4.2. Statuant sur renvoi, la cour cantonale a admis que les documents transmis par le recourant démontraient que celui-ci était connu depuis de nombreuses années sous le nom de A._ B._ (avec ou sans trait d'union), tant par les autorités françaises et suisses que par des tiers. Cette circonstance n'était cependant pas déterminante. Si le droit français permettait certes l'utilisation du nom de ses deux parents, ce nom d'usage n'était pas reconnu à l'état civil, ni transmissible. Se fonder sur les arguments de la durée du port du nom et du souhait personnel de le conserver ne pouvait ainsi constituer un motif légitime. En droit suisse, le nom d'usage n'était pas connu de la législation, en sorte que le recourant ne pouvait y trouver un motif légitimant son désir de porter celui qu'il avait adopté de son propre gré. La cour cantonale a par ailleurs relevé que la divergence entre la réalité administrative, privée, personnelle, sociale et professionnelle du recourant et son nom inscrit au registre d'état civil lui était entièrement imputable, si bien qu'il ne pouvait s'en prévaloir. Quant à l'importance objective du patronyme adopté dans sa vie économique, elle n'était pas démontrée: si le patronyme de B._ était favorablement connu sur les marchés immobiliers, l'intéressé n'établissait pas avoir subi un préjudice au cours des six dernières années, période durant laquelle il n'avait été qu'au bénéfice exclusif du patronyme A._, tel qu'inscrit sur sa carte d'identité et dans le registre fédéral Infostar; l'acte de notoriété du 13 mai 1981 attestait au demeurant qu'il n'était pas exclusivement connu dans son milieu professionnel sous le nom de A._-B._. Les juges cantonaux ont également considéré que les pièces déposées par le recourant ne permettaient pas de conclure qu'il serait particulièrement lésé par son nom, ni qu'il disposerait d'un intérêt spécifique à conserver le nom sous lequel il était connu. Aucun motif en relation avec le nom lui-même n'était enfin à relever.
4.3. Actif dans l'immobilier, le recourant soutient pour l'essentiel être connu depuis quarante ans et ce sans discontinuité sous le nom de A._ B._: ses amis, connaissances et relations professionnelles, de même que les autorités administratives suisses et françaises, la République française, et notamment le Ministère de l'intérieur, s'adresseraient à lui sous ce nom, de sorte qu'il disposerait d'un motif légitime à réclamer le changement de nom sollicité. Le recourant affirme également avoir un intérêt d'ordre moral et affectif à la modification qu'il réclame. Il indique à cet égard souffrir quotidiennement de la différence entre son état civil suisse - A._ - et le nom sous lequel il est connu de tous - A._ B._ -, divergence nécessitant une justification constante et entraînant une perte de crédibilité à son égard. Le patronyme B._ le rattacherait du reste à la famille de son grand-père maternel, célèbre architecte, constructeur et propriétaire immobilier, dont il avait reçu un métier, des immeubles connus comme étant les " immeubles B._ " ainsi qu'un nom commercial constituant depuis des dizaines d'années une véritable marque.
4.4. Ainsi que le relève à juste titre l'autorité cantonale, le recourant a lui-même pris l'initiative, de longue date, d'accoler le nom de sa mère à son nom légal, décidant de se présenter et de se faire appeler sous ce double patronyme, qu'il s'était personnellement choisi. S'il est certes lui-même à l'origine des inconvénients qu'il prétend subir actuellement, il n'en demeure pas moins que sa démarche ne paraît pas procéder d'une simple " lubie " que la révision législative de 2011 ne permettrait pas de concrétiser. Bien que les motifs subjectifs qu'il invoque (principalement le rattachement à un ancêtre illustre) ne paraissent pas d'une intensité suffisante pour retenir une violation du pouvoir d'appréciation de l'autorité cantonale et fonder le changement sollicité, les différentes pièces qu'il a produites (pour l'essentiel: contrats, actes judiciaires et administratifs, carte d'assurance-maladie établie au nom de A._-B._, carte d'identité française reproduisant ce nom d'usage) démontrent qu'il est manifestement connu de l'administration ainsi que de son entourage privé et professionnel sous le nom de A._ B._ et ce depuis plusieurs dizaines d'années; elles attestent ainsi l'importance objective que revêt depuis longtemps le nom qu'il souhaite officialiser dans sa vie sociale, professionnelle et administrative. Or en exigeant que l'intéressé soit " spécialement lésé " par son nom officiel actuel, la cour cantonale s'est référée à un critère qui n'est plus déterminant au regard de l'assouplissement législatif entré en vigueur en 2013 et a ainsi violé le pouvoir d'appréciation qui lui était conféré.
La présente situation revêt, il est vrai, un caractère singulier du fait que le recourant sollicite de pouvoir porter un double nom. Quoique relativement rares, les doubles noms existent en Suisse (cf. pour des exemples: GEISER, op. cit., n. 3.41). Cette particularité doit être distinguée de la possibilité pour l'époux (se) de porter un double nom légal, désormais supprimée avec l'entrée en vigueur de la législation susmentionnée. Cette modification législative était cependant liée à l'égalité de traitement entre l'homme et la femme lors du choix du nom des époux au moment de la conclusion de l'union (DE LUZE/DE LUIGI, Le nouveau droit du nom, in: PJA 2013 505 ss, p. 508 et les références), circonstance distincte de celle prévalant en l'espèce. Cette question est au demeurant toujours discutée dès lors que, le 15 décembre 2017, le conseiller national Luzi Stamm a déposé une initiative parlementaire visant à autoriser le double nom en cas de mariage (initiative no 17.523). L'on notera certes que, par sa requête, le recourant sollicite l'attribution d'un double nom composé du patronyme de chacun de ses parents. Il s'agit toutefois ici de faire coïncider son identité officielle avec son identité administrative, sociale et professionnelle. Sa situation diffère dès lors de celle de l'enfant auquel l'on refuse la possibilité de porter le double nom de son père et de sa mère et pour lequel ce simple souhait ne répond pas à un motif légitime dans le sens interprété ci-dessus (<ref-ruling> consid. 4).
5.
En définitive, le recours doit être admis, l'arrêt cantonal annulé et la demande de changement de nom du recourant admise en ce sens que son nom de famille est désormais A._ B._. Il est statué sans frais (<ref-law>), l'intimé devant toutefois s'acquitter d'une indemnité de dépens en faveur du recourant (art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt cantonal annulé et la demande de changement de nom du recourant admise en ce sens que son nom de famille est désormais A._ B._, le registre d'état civil étant modifié en conséquence.
2.
Il n'est pas perçu de frais judiciaires.
3.
Une indemnité de 2'500 fr., à verser au recourant à titre de dépens, est mise à la charge de l'intimé.
4.
Le présent arrêt est communiqué aux parties, à la Cour de droit public du Tribunal cantonal du canton du Valais et au Département fédéral de justice et police.
Lausanne, le 26 octobre 2018
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : von Werdt
La Greffière : de Poret Bortolaso