Faits:
A.
Ressortissant kosovar né en 1974, A.X._ est entré en Suisse en 1997 et y a déposé une demande d'asile qui a été définitivement rejetée le 5 juin 2000. Le 26 mai 2000, il a épousé B._, ressortissante suisse née en 1952, et a de ce fait obtenu une autorisation de séjour le 22 décembre 2000, qui a été régulièrement renouvelée jusqu'en mai 2004. Aucun enfant n'est issu de cette union.
Le 31 août 2004, l'Office fédéral des migrations (ci-après: l'Office fédéral) a accordé la nationalité suisse par voie facilitée à A.X._ du fait de son mariage avec une Suissesse. Les époux ont introduit une requête commune de divorce le 26 septembre 2005; leur mariage a été dissout le 30 janvier 2006. Le 18 octobre 2006, l'Office de l'état civil de Martigny (VS) a délivré à A.X._ un certificat de capacité matrimoniale en vue de son mariage, le 7 février 2007, avec une ressortissante kosovare née en 1985 et domiciliée au Kosovo. Par décision du 8 novembre 2007, subséquemment confirmée par le Tribunal administratif fédéral et par le Tribunal fédéral (arrêt 1C_129/2009 du 26 mai 2009), l'Office fédéral a annulé la naturalisation facilitée accordée à A.X._, au motif que son union avec B._ ne pouvait pas être considérée comme une communauté conjugale effective et stable et que la naturalisation facilitée avait été obtenue sur la base de déclarations mensongères, voire d'une dissimulation de faits essentiels.
B.
Privé de titre de séjour valable en Suisse ensuite de la révocation de la nationalité suisse, A.X._ a requis l'octroi d'une autorisation de séjour le 1er septembre 2009. Par décision du 26 octobre 2010, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a rejeté cette demande et prononcé le renvoi de Suisse de A.X._, dont le recours contre cette décision a été rejeté par le Conseil d'Etat valaisan le 22 août 2012. Le recours formé par A.X._ contre la décision du 22 août 2012 a, à son tour, été rejeté par arrêt du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) du 8 mai 2013.
C.
Agissant par la voie du recours en matière de droit public contre l'arrêt du 8 mai 2013, A.X._ demande au Tribunal fédéral, principalement, son annulation et, subsidiairement, l'octroi d'une autorisation de séjour en Suisse. Le Tribunal cantonal et le Service cantonal renoncent à se déterminer; le Conseil d'Etat valaisan et l'Office fédéral proposent le rejet du recours.
Par ordonnance présidentielle du 17 juin 2013, le Tribunal fédéral a admis la requête d'effet suspensif formée par le recourant.

Considérant en droit:
1.
La loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) est entrée en vigueur le 1er janvier 2008, abrogeant la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (aLSEE). En vertu de l'art. 126 al. 1 LEtr, les demandes déposées avant le 1er janvier 2008 sont régies par l'ancien droit.
Etant donné que le recourant a sollicité une autorisation de séjour le 1er septembre 2009, sa cause est soumise au nouveau droit (cf. consid. 4.1 infra). Que le recourant ait jusqu'alors pu résider en Suisse en raison de son mariage avec une Suissesse, union qui avait été dissoute sous l'empire de l'ancien droit, est sans pertinence; grâce à l'effet suspensif accompagnant ses recours contre la révocation de la naturalisation facilitée, le recourant avait en effet bénéficié du titre, certes précaire, de séjourner en Suisse au-delà de l'entrée en vigueur de la LEtr (cf. arrêts 2C_869/2010 du 19 avril 2011 consid. 2.3 in fine; 2C_411/2010 du 9 novembre 2010 consid. 1, non publié in <ref-ruling>).
2.
2.1. Selon l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral, ni le droit international ne donnent droit. Le recourant invoque l'art. 50 al. 1 LEtr selon lequel, après dissolution de la famille, le droit du conjoint à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité subsiste dans certains cas. Dès lors qu'il n'est pas d'emblée exclu que cette disposition soit applicable et que ses conditions soient remplies, il convient d'admettre un droit de recourir sous l'angle de l'art. 83 let. c ch. 2 LTF. Le recourant a en effet potentiellement un droit à l'autorisation sollicitée, le point de savoir si c'est à juste titre que les autorités cantonales en ont nié l'application et ont retenu une situation d'abus de droit relevant du fond et non de la recevabilité (cf. <ref-ruling> consid. 1.1 p. 179).
Tel n'est en revanche pas le cas s'agissant de la violation alléguée de l'art. 30 LEtr, puisque cette disposition ne confère pas un droit à une autorisation de séjour (arrêts 2C_68/2013 du 25 mars 2013 consid. 1.2; 2C_400/2011 du 2 décembre 2011 consid. 1.2.2), si bien que le recours est irrecevable la concernant. Il l'est également s'il devait être considéré comme recours constitutionnel subsidiaire, puisque le recourant n'invoque la violation d'aucun droit constitutionnel (art. 113 et 116 LTF; cf. arrêt 2C_377/2013 du 7 mai 2013 consid. 3).
2.2. Pour le surplus, le recours est dirigé contre une décision finale (<ref-law>), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et 2 LTF). Déposé en temps utile (<ref-law>) et dans les formes prescrites (<ref-law>), par le destinataire de l'arrêt attaqué qui a qualité pour recourir au sens de l'<ref-law>, le recours en matière de droit public est par conséquent recevable.
3.
Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'<ref-law>. Aux termes de cet alinéa, le Tribunal fédéral n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par le recourant.
Hormis ces domaines, le Tribunal fédéral n'est pas lié par les motifs de l'autorité précédente ni par les moyens des parties; il peut donc admettre le recours pour d'autres motifs que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 1.4 p. 400; arrêt 2C_349/2012 du 18 mars 2013 consid. 2.1).
En outre, le Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ceux-ci n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (<ref-ruling> consid. 7.1 p. 51; <ref-ruling> consid. 4.2 p. 560) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente (cf. <ref-law>), il doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées. Sinon, il n'est pas possible de tenir compte d'un état de fait divergeant de celui qui est contenu dans l'acte attaqué. Les faits et les critiques invoqués de manière appellatoire sont irrecevables (<ref-ruling> consid. 3 p. 104).
4.
4.1. Le recourant s'en prend à l'arrêt attaqué principalement au motif que ce dernier a appliqué l'ancien droit (aLSEE) à son cas, alors que, selon l'intéressé, la disposition plus favorable de l'art. 50 LEtr, dont il estime du reste remplir l'ensemble des conditions pour pouvoir demeurer en Suisse, aurait dû trouver à s'appliquer en l'occurrence. Le Tribunal cantonal a quant à lui justifié l'application de l'ancien droit des étrangers par le fait que tant le mariage que le divorce des époux X._, dont le recourant entendait déduire un droit de séjour, étaient intervenus sous l'empire de l'aLSEE, le principe de la lex mitior invoqué par le recourant ne s'appliquant par ailleurs qu'aux dispositions pénales, en vertu de l'art. 126 al. 4 LEtr. Or, comme il a été vu (consid. 1 supra), ledit critère retenu par le Tribunal cantonal n'est pas conforme à l'art. 126 al. 1 LEtr a contrario, selon lequel c'est le jour du dépôt de la demande d'autorisation de séjour litigieuse - soit le 1er septembre 2009 - qui détermine en principe le droit matériel applicable, ici la LEtr. Sur ce point, le recourant a donc raison, mais cela ne signifie pas pour autant que son recours doive être admis pour ce motif.
4.2. Le recourant s'était vu conférer une autorisation de séjour le 22 décembre 2000 qui avait été régulièrement renouvelée jusqu'au 25 mai 2004; n'ayant pas été renouvelée subséquemment, elle s'était toutefois éteinte, conformément à l'art. 61 al. 1 let. c LEtr. Elle n'existait plus (contrairement à ce que l'arrêt attaqué a retenu à son consid. 3.3, en contradiction avec la let. B de l'état de fait et les pièces au dossier; <ref-law>) lorsque le recourant a obtenu la naturalisation facilitée, le 31 août 2004. Au moment de la révocation de la naturalisation, la question d'une éventuelle réactivation du statut antérieur en droit des étrangers du recourant (cf. <ref-ruling> consid. 3 p. 5 ss; arrêts 2C_682/2012 du 7 février 2013 consid. 6.1; 2C_563/2010 du 16 août 2010 consid. 2), échu auparavant, ne se posait dès lors pas. Seule entre ainsi en considération l'hypothèse du droit à l'octroi d'une autorisation de séjour à la suite de la dissolution de la famille, selon l'art. 50 LEtr, et non celle de sa prolongation (cf. consid. 5 infra).
5.
5.1. En vertu de l'art. 50 al. 1 LEtr, après dissolution de la famille, le droit du conjoint et des enfants à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 subsiste dans les cas suivants: l'union conjugale a duré au moins trois ans et l'intégration est réussie (let. a); la poursuite du séjour en Suisse s'impose pour des raisons personnelles majeures (let. b). D'après l'art. 51 al. 2 let. a LEtr, les droits prévus aux art. 43, 48 et 50 LEtr s'éteignent toutefois lorsqu'ils sont invoqués abusivement, notamment pour éluder les dispositions de la loi sur les étrangers sur l'admission et le séjour ou ses dispositions d'exécution.
5.2. Ce n'est que lorsque les conditions d'application de l'art. 50 al. 1 let. a LEtr sont réalisées, ce qui suppose que l'union conjugale entre l'étranger et son conjoint suisse ou titulaire d'une autorisation d'établissement a effectivement duré trois ans, qu'il faut se demander, en fonction de l'existence d'indices, si les conjoints ont seulement cohabité pour la forme et si la durée de la communauté conjugale, compte tenu de l'interdiction de l'abus de droit (art. 51 LEtr), ne doit pas être prise en compte ou ne l'être que partiellement (<ref-ruling> consid. 3.2 in fine p. 117; arrêt 2C_177/2013 du 6 juin 2013 consid. 3.1; cf. aussi arrêts 2C_682/2012 du 7 février 2013 consid. 6.2.2; 2C_839/2010 du 25 février 2011 consid. 7.2).
En l'occurrence, le mariage du recourant avec sa première épouse de nationalité suisse a duré du 26 mai 2000 jusqu'au prononcé du divorce le 30 janvier 2006. La requête de divorce confirmant la désunion du couple a cependant été introduite le 26 septembre 2005; il ressort en outre de la procédure diligentée à l'encontre de la révocation de la naturalisation du recourant que, selon les dires de sa première ex-épouse, les problèmes conjugaux, attribués à une incompatibilité d'humeur, étaient survenus à partir du début de l'année 2005 et que son ex-mari aurait quitté le domicile conjugal environ quatre mois plus tard (arrêt 1C_129/2009 du 26 mai 2009, let. B). Quoi qu'il en soit de la date exacte de la fin de l'union conjugale des époux, sa durée a donc formellement dépassé le seuil minimum de trois ans requis par l'art. 50 al. 1 let. a LEtr. En tant que l'arrêt querellé a retenu des indices supposés corroborer l'existence d'un mariage fictif, il y a donc lieu, avant d'examiner si les autres conditions de l'art. 50 LEtr seraient par hypothèse remplies, de vérifier si lesdits éléments confirment ou non la nature abusive du mariage contracté par les époux X._.
Il sera encore précisé qu'au vu des considérations qui suivent en lien avec l'abus de droit, la question de savoir si le remariage du recourant avec une ressortissante kosovare, domiciliée au Kosovo et dépourvue de titre de séjouren Suisse, lui permettait encore de se prévaloir de l'art. 50 LEtr en lien avec son précédent mariage avec une Suissesse (art. 42 LEtr; cf. <ref-ruling> consid. 3.2.1 p. 348 s.; arrêt 2C_590/2010 du 29 novembre 2010 consid. 2.5.3), souffre de rester ouverte.
5.3. Le Tribunal fédéral a jugé que la jurisprudence rendue sous l'ancien droit en matière de mariage abusif pouvait être reprise sous le nouveau droit (arrêts 2C_177/2013 du 6 juin 2013 consid. 3.2; 2C_811/2010 du 23 février 2011 consid. 4.4.1).
5.3.1. Il y a mariage fictif lorsque celui-ci est contracté dans le seul but d'éluder les dispositions de la loi fédérale sur les étrangers, 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. <ref-ruling> consid. 4a p. 55; arrêt 2C_222/2008 du 31 octobre 2008 consid. 3.3 in fine et 4.3). 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 paraît définitivement rompue, faute de chances de réconciliation entre les époux (cf. <ref-ruling> consid. 4.2 p. 117; <ref-ruling> consid. 2 et 3 p. 151 s.). Dans l'une et l'autre de ces hypothèses, l'intention réelle des époux ne peut souvent pas être établie par une preuve directe, mais seulement grâce à des indices (cf. <ref-ruling> consid. 5a p. 57; arrêt 2C_177/2013 du 6 juin 2013 consid. 3.2).
5.3.2. Constituent notamment les indices d'un mariage fictif ou d'un abus de droit le fait que l'époux étranger soit menacé d'un renvoi ou ne puisse obtenir une autorisation de séjour autrement que par un mariage; l'existence d'une sensible différence d'âge entre les époux; les circonstances particulières de leur rencontre et de leur relation, tels une courte période de fréquentation avant le mariage ou le peu de connaissances que les époux ont l'un de l'autre, etc. (parmi de nombreuses références, cf. <ref-ruling> consid. 2b p. 295; arrêts 2C_587/2008 du 4 décembre 2008 consid. 4.1; 2C_222/2008 du 31 octobre 2008 consid. 3.3).
5.3.3. Selon la jurisprudence, un mariage fictif existe même si l'un seul des époux a contracté mariage en vue d'éluder la loi sur les étrangers, tandis que l'autre désirait sincèrement fonder une communauté de vie avec son conjoint. Toutefois, dans la plupart des cas soumis au Tribunal fédéral, de tels couples connaissaient assez tôt d'importantes difficultés relationnelles, quand ils ne volaient pas en éclats à brève échéance. C'est pourquoi, lorsque la vie commune a présenté une certaine durée et qu'il n'apparaît pas de manière manifeste qu'elle soit de pure façade, la jurisprudence pose des exigences relativement élevées pour admettre l'existence d'un mariage fictif sur la seule base d'indices. Ceux-ci doivent alors être clairs et concrets. En outre, la preuve d'un mariage fictif doit être apportée par l'autorité, sous réserve de l'obligation des parties de collaborer à l'établissement des faits. Cette obligation des parties est d'autant plus grande que les circonstances objectives du cas permettent de douter de la réelle et commune volonté des époux de former une communauté de vie. En présence d'indices sérieux d'un mariage fictif, il appartient aux parties de démontrer, par une argumentation circonstanciée, l'existence d'une relation conjugale réellement vécue et voulue (arrêt 2C_177/2013 du 6 juin 2013 consid. 3.4 et les nombreuses références citées).
5.3.4. Les constatations portant sur les indices peuvent concerner des circonstances externes tout comme des éléments d'ordre psychique relevant de la volonté interne (volonté de chacun des époux). Il s'agit, dans les deux cas, de constatations de fait (ATF <ref-ruling> consid. 2.3 p. 152 et les arrêts cités) qui lient le Tribunal fédéral, sauf si elles ont été établies de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (consid. 3 supra). En revanche, le Tribunal fédéral examine librement si les constatations de fait (indices) permettent de conclure à l'existence d'un mariage fictif.
5.4. En l'espèce, les précédents juges ont nié la réalité de l'union conjugale ab initio, en considérant que le mariage avait été conclu dans le but de permettre au recourant de demeurer en Suisse en contournant la législation en matière d'étrangers. Ce faisant, le Tribunal cantonal s'est en particulier fondé sur les éléments suivants: le recourant avait épousé une ressortissante suisse à une époque où sa demande d'asile avait été rejetée en première instance; la dissolution du mariage consécutivement à l'obtention de la naturalisation facilitée par l'intéressé n'avait été précédée par aucun événement particulier susceptible de l'expliquer; elle avait en outre été suivie, peu de temps après, par le remariage du recourant avec une ressortissante du Kosovo.
L'instance précédente s'est de plus expressément référée à la procédure que l'Office fédéral avait initiée en vue de la révocation de la naturalisation facilitée et qui, en dernière instance, avait été sanctionnée par le Tribunal fédéral (arrêt 1C_129/2009 du 26 mai 2009). A cet égard, le Tribunal fédéral avait confirmé la position du Tribunal administratif fédéral selon laquelle l'on pouvait douter que le recourant ait réellement voulu constituer une véritable communauté conjugale (arrêt 1C_129/2009 du 26 mai 2009 consid. 4.1) et que les éléments retenus et leur enchaînement chronologique relativement rapide étaient de nature à fonder la présomption que l'intéressé avait choisi d'épouser une ressortissante suisse dans le but prépondérant de s'installer dans ce pays et d'en obtenir ultérieurement la nationalité (cf. arrêt du Tribunal administratif fédéral du 18 février 2009 consid. 6.2). L'hypothèse d'un mariage de complaisance était en outre corroborée par le laps de temps entre la déclaration des époux confirmant leur vie en communauté conjugale (14 juin 2004), l'octroi de la naturalisation facilitée (31 août 2004), la requête commune de divorce (26 septembre 2005) et les démarches entreprises par le recourant en vue d'épouser une ressortissante kosovare (18 octobre 2006). S'ajoutait à cela, deuxièmement, le fait que le recourant avait épousé une ressortissante suisse en mai 2000, alors qu'il faisait l'objet d'une procédure de refus d'asile et de renvoi de Suisse et que ses conditions de séjour paraissaient précaires. Troisièmement, le recourant avait épousé une femme de vingt-deux ans son aînée, situation inhabituelle dans son milieu socio-culturel. Quatrièmement, moins d'une année après son divorce, il avait entrepris des démarches en vue de contracter mariage avec une compatriote trente-trois ans plus jeune que sa première épouse. Cinquièmement et finalement, les déclarations des ex-époux lors des différentes auditions avaient présenté des divergences (arrêt 1C_129/2009 précité, consid. 4.1). Au vu de ces éléments, l'on pouvait présumer que le recourant avait obtenu sa naturalisation frauduleusement, présomption qu'il n'était du reste pas parvenu à affaiblir (arrêt 1C_129/2009 précité, consid. 4.1 in fine).
5.5. Compte tenu des nombreux indices retenus tant par les précédents juges que dans le cadre de la procédure de révocation de la naturalisation à laquelle ceux-ci se sont référés (indices qui n'étaient pas uniquement propres à retenir que la naturalisation facilitée avait été obtenue à l'aide d'une déclaration mensongère, mais étaient également pertinents pour l'appréciation du mariage en droit des étrangers), il n'apparaît ainsi pas choquant que les juges cantonaux aient retenu que la relation vécue par le recourant avec sa première ex-épouse n'avait été que de pure complaisance dès ses débuts. Il n'est notamment pas arbitraire d'admettre que le lien des époux X._ s'expliquait par l'intérêt à ce que le recourant puisse, de son point de vue, demeurer et travailler en Suisse et y acquérir un titre de séjour durable, puis la naturalisation suisse facilitée grâce à son mariage avec une ressortissante suisse. Dès l'obtention de la naturalisation facilitée, il lui était ensuite possible de divorcer d'avec sa première épouse et de convoler avec une femme plus proche de son âge et de son milieu socio-culturel.
5.6. Par conséquent, les juges cantonaux ont, de manière claire et soutenable, considéré que le mariage des ex-époux X._ avait été dénué de substance dès ses débuts, si bien que le recourant serait mal venu d'invoquer l'art. 50 LEtr pour en tirer un quelconque droit de demeurer en Suisse au bénéfice d'une autorisation de séjour, ensuite de la révocation de la naturalisation facilitée en sa faveur (cf. art. 51 al. 1 let. a LEtr).
5.7. L'argument qu'oppose le recourant, d'après lequel le Tribunal cantonal n'aurait pas eu le droit de faire abstraction de l'union conjugale des ex-époux au regard de l'art. 50 LEtr tant que le mariage n'avait pas été dissout dans le cadre d'une procédure d'annulation du mariage au sens du Code civil suisse (dont l'art. 105 ch. 4 fonde une cause d'annulation lorsque l'un des époux ne veut pas fonder une communauté conjugale mais éluder les dispositions sur l'admission et le séjour des étrangers), ne lui est d'aucun secours.
D'une part, il ne tient compte ni de la nature même de l'abus de droit (cf. art. 51 LEtr et <ref-law>), qui permet précisément de faire abstraction d'un droit, en l'occurrence l'institution juridique du mariage, dont l'exercice n'a été, comme ici, que de pure façade, ni de la circonstance que l'application de l'art. 50 LEtr ne dépend pas de l'extinction formelle du mariage, mais de la fin de la communauté conjugale réellement vécue (<ref-ruling> consid. 2 p. 231; <ref-ruling> consid. 3.1.2 p. 347). Au demeurant, le recourant perd de vue qu'au moment où les autorités s'étaient aperçues de l'abus de droit, son mariage avec sa première épouse s'était déjà terminé par le divorce.
D'autre part, ce n'est pas parce que, sur le plan du droit civil, le mariage du recourant avec sa première épouse n'a pas été annulé, mais a été dissout par le divorce que les procédures engagées en parallèle sur le terrain du droit public des étrangers ne pouvaient pas suivre leur cours. Il sera à ce titre précisé qu'en introduisant dans le Code civil une cause d'annulation du mariage permettant de combattre les mariages de complaisance (<ref-law>), le législateur a entendu renforcer la lutte contre ce phénomène et non pas limiter, voire entraver l'application des sanctions qui étaient déjà prévues en droit public des étrangers ainsi qu'en droit pénal (cf., à ce sujet, Message du 8 mars 2002 concernant la loi sur les étrangers, in FF 2002 3469, p. 3513 ch. 1.3.7.8).
6.
Le recourant soutient que l'arrêt attaqué heurterait le principe de la proportionnalité. Il fait à ce titre valoir son long séjour (seize ans) et sa bonne intégration en Suisse (résidence continue à Riddes; travail ininterrompu dans la même entreprise; absence d'infractions commises), la quasi-absence de contacts avec son pays d'origine, ainsi que le séjour de ses frères et soeurs en Suisse.
6.1. Dans la mesure où le recourant a déjà séjourné en Suisse depuis de nombreuses années et où l'arrêt entrepris a pour résultat de l'empêcher de demeurer sur le territoire helvétique, la question de la proportionnalité se pose. Exprimé de manière générale à l'art. 5 al. 2 Cst. et découlant également de l'art. 96 LEtr, ce principe exige que la mesure prise par l'autorité soit raisonnable et nécessaire pour atteindre le but d'intérêt public ou privé poursuivi (cf. <ref-ruling> consid. 3.2 p. 91 s.; <ref-ruling> consid. 4.2 p. 380).
6.2. En l'espèce, on ne voit pas que la décision déniant au recourant l'octroi d'une autorisation de séjour, alors qu'il ne disposait (plus) d'aucun droit à résider en Suisse par suite de l'expiration de son autorisation de séjour en 2004, de la révocation de la naturalisation facilitée en 2007 et du constat qu'il avait mené un mariage de complaisance ab initio avec une ressortissante suisse soit disproportionnée.
Arrivé en Suisse en 1997, à l'âge de presque vingt-trois ans, le recourant a passé toute son enfance et son adolescence au Kosovo. Bien qu'il faille lui reconnaître un certain degré d'intégration au vu de l'obtention de la naturalisation facilitée en 2004, le recourant ne peut néanmoins pas avancer des motifs prépondérants qui plaideraient en faveur du maintien de son séjour en Suisse; en particulier, il est sans enfant en Suisse et ne fait point valoir ni n'établit que des liens exceptionnels le lieraient à ses frères et soeurs vivant en Suisse, que ses contacts avec son pays d'origine seraient entièrement coupés ou encore qu'il serait empêché de trouver, au Kosovo, du travail similaire à celui qu'il exerce actuellement pour une coopération fruitière.
6.3. Compte tenu de l'ensemble des circonstances, il n'apparaît pas qu'en faisant primer l'intérêt public à éloigner le recourant sur l'intérêt privé de celui-ci de rester en Suisse, le Tribunal cantonal ait méconnu les art. 5 al. 2 Cst. ou 96 LEtr. Le grief tiré de la violation du principe de proportionnalité doit donc être écarté.
7.
Il résulte de ce qui précède que le recours doit être rejeté en tant qu'il est recevable. Les frais seront mis à la charge du recourant qui succombe (<ref-law>). 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é dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au mandataire du recourant, au Service de la population et des migrations du canton du Valais, au Conseil d'Etat du canton du Valais, au Tribunal cantonal du canton du Valais, Cour de droit public, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 5 décembre 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Chatton