Faits :
A.
A._, dit A._-B._, est né le... 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 2011 en Suisse 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.
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._.
C.
Agissant le 19 septembre 2017 par la voie du recours en matière de droit public au Tribunal fédéral, 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._.
Le Conseil d'État se réfère aux considérants de l'arrêt entrepris; le Tribunal cantonal ne s'est pas déterminé.

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_334/2014 du 23 octobre 2014 consid. 1.1 non publié aux <ref-ruling>). La désignation erronée de la voie de droit ne nuit toutefois pas au recourant si son recours remplit les exigences légales de celle qui lui est ouverte (<ref-ruling> consid. 1.1; <ref-ruling> consid. 1.2), ce qui est le cas en l'espèce: la décision, de nature non pécuniaire, a été prise en dernière instance cantonale et sur recours par un tribunal supérieur (<ref-law>); le recourant, qui a la qualité pour recourir (<ref-law>), a formé son recours à temps (<ref-law>).
2.
2.1. Saisi d'un recours en matière civile, le Tribunal fédéral applique en principe d'office le droit (<ref-law>) à l'état de fait constaté dans l'arrêt cantonal. Il n'est pas lié par les motifs de l'autorité précédente ou les moyens des parties; il peut admettre le recours en se fondant sur d'autres arguments que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 1.3; <ref-ruling> consid. 1.4).
2.2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>); il ne peut s'en écarter que si ces faits ont été constatés 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'influencer le sort de la cause (<ref-law>). La partie recourante 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. 2.3), doit démontrer, par une argumentation précise, en quoi consiste la violation (<ref-law>; <ref-ruling> consid. 3.3; <ref-ruling> consid. 2.2).
3.
3.1. En principe, le nom d'une personne est immuable (<ref-ruling> consid. 3.2; <ref-ruling> 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 parlementairesen lien avec l'initiative parlementaire 03.428 (Leutenegger Oberholzer). La condition des " motifs légitimes " vise à diminuer les obstacles au changement de nom, sans pour autant ouvrir la possibilité à quiconque de modifier son nom à sa guise (<ref-ruling> consid. 3.3.3 et les références). Les motifs légitimes doivent ainsi être appréciés de manière plus souple que les " justes motifs " (<ref-ruling> consid. 3.3.4; 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), étant précisé que la requête doit toujours faire état de motifs particuliers (MEIER/DE LUZE, op. cit., n. 292), lesquels ne peuvent être illicites, abusifs ou contraires aux moeurs (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). 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 (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>; décision NT160001 de l'Obergericht du canton de Zurich du 29 juin 2016 consid. III.1; décision du Kantonsgericht du canton de Lucerne du 24 septembre 2015 consid. 4.1 publié in CAN - Zeitschfrift für kantonale Rechtsprechung 2016 Nr. 1 p. 8 et in LGVE 2015 I Nr. 15; décision du Sicherheits-und Justizdepartement du canton d'Obwald du 7 novembre 2014 consid. 3 publié in OGVE 2014/2015 Nr. 50 p. 280; plus restrictifs: STEINAUER/FOUNTOULAKIS, op. cit., n. 411 et GUILLOD, Droit des personnes, 4e éd. 2015, n. 53). 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.
A noter que la doctrine estime par ailleurs que l'officialisation d'un pseudonyme pourrait constituer un motif légitime de changement de nom lorsque les conditions pour qu'il figure sur le passeport à titre de complément officiel seraient remplies, le requérant devant alors démontrer que son nom d'artiste a une importante 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.; GEISER, op. cit., n. 3.33; cf. l'art. 2 al. 4 de la loi fédérale sur les documents d'identité des ressortissants suisses [LDI], RS 143.1 et le site de l'administration fédérale: https://www.schweizerpass.admin.ch/pass/fr/home/ausweise/inhalt/ergaenzungen.html; cf. également AEBI-MÜLLER, in Handkommentar zum Schweizer Privatrecht, 3e éd. 2016, n. 10 ad <ref-law>, qui précise toutefois que l'action de l'<ref-law> demeure réservée; 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. La cour cantonale a retenu que le recourant avait lui-même pris l'initiative de se présenter et de se faire appeler A._ B._. Il fallait dès lors retenir que la modification envisagée visait en réalité à changer de nom selon ses souhaits, projet dont le législateur avait clairement dit que sa réalisation n'avait pas à être facilitée par la teneur actuelle de l'<ref-law>. La démarche du recourant se rapprochait finalement d'une requête de changement de nom visant à officialiser un pseudonyme. Or il était rationnel de penser que l'<ref-law> ne le permettait pas, à l'instar de l'ancien droit. A supposer au demeurant qu'une telle démarche fût permise au regard du nouveau droit, la cour cantonale a jugé que les allégations du recourant sur la quasi nécessité que serait pour lui l'octroi de l'autorisation de changement de nom n'étaient corroborées par aucune pièce analogue à des contrats ou à d'autres documents provenant de tiers telles des coupures de presse, etc. L'unique source documentaire extérieure au dossier se réduisait à un site internet géré par le recourant, qui ne permettait pas de démontrer que le changement de nom sollicité avait une importance objective dans la vie économique et sociale de l'intéressé.
4.2. Le recourant reproche à l'autorité cantonale d'avoir arbitrairement constaté les faits en omettant de tenir compte de différentes pièces (administratives ou judiciaires pour l'essentiel) attestant qu'il portait le patronyme A._ B._ depuis plus de 40 ans, et ce de manière continue.
Postérieurement à sa décision, le Tribunal cantonal a reconnu que ces pièces se trouvaient au dossier, sans donner d'explications quant à son refus d'en tenir compte. Or dites pièces, émanant de tiers, sont déterminantes pour l'issue du litige dès lors qu'elles sont susceptibles d'établir l'éventuelle importance du changement de nom réclamé par le recourant dans sa vie sociale et économique. Il convient donc d'admettre la critique de l'intéressé sur ce point et de retourner la cause à la cour cantonale afin qu'elle rende une décision en procédant à une appréciation préalable de ces différents éléments de preuve, qu'elle a ignorés à tort.
5.
En définitive, le recours est admis, l'arrêt cantonal annulé et l'affaire retournée à la cour cantonale pour nouvelle décision au sens des considérants. 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 cause renvoyée à la cour cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Une indemnité de 3'000 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 et à la Cour de droit public du Tribunal cantonal du canton du Valais.
Lausanne, le 22 janvier 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