Sachverhalt:
A.
A._ ist Eigentümer der in der Landwirtschaftszone der Gemeinde Finhaut gelegenen Parzelle Nr. xxx (Plan Nr. xxx, im Ort "Les Tsantons"), auf der ein Chalet erstellt ist . Zur Abrundung des Terrains und zur Erstellung eines Parkplatzes am Rand der Strasse stellte er am 22. November 2000 ein Gesuch an das Departement für Verkehr, Bau und Umwelt (DVBU), um die angrenzende, im Eigentum des Kantons Wallis stehende Parzelle Nr. yyy (früher Nr. yyy) zu erwerben. Mit Schreiben vom 20. August 2003 ermächtigte ihn der Rechtsdienst des DVBU, auf eigenes Risiko ("à vos risques et périls") die notwendigen Vorkehren zu treffen, um bei der Gemeinde ein Baugesuch zur Errichtung des Parkplatzes auf kantonalem Boden einzureichen. Mit Schreiben vom 18. November 2003 teilte die Gemeinde A._ mit, das Baugesuch sei angenommen worden, fügt aber auch an "la présente autorisation ne préjuge en rien des décisions que seront appelées à prendre les autorités compétentes pour ce qui a trait à l'autorisation de construire et à l'utilisation du domaine public".
B.
Am 2. September 2004 reichte die Landschaftsgärtnerei B._ SA für A._ bei der Gemeinde ein Gesuch für die Erstellung eines Schwimmbads neben dem Chalet ein, wobei eine Teilfläche des Beckens (14 m2 ) auf den kantonalen Grund (Parzelle Nr. yyy) hinüber ragen würde. Mit Schreiben vom 8. September 2004 verlangte die Gemeinde nähere Angaben zum Bauprojekt und hielt unter anderem fest, für die Baute ausserhalb der Bauzone sei eine Ausnahmebewilligung nach Art. 24 RPG erforderlich.
C.
Am 30. September 2004 gelangte A._ an die Dienststelle für Strassen- und Flussbau des DVBU und beantragte erneut den Kauf der Parzelle Nr. yyy. Am 18. November 2004 informierte die Dienststelle A._ über die Weiterleitung des Gesuchs mit einer positiven Vormeinung an den Verwaltungs- und Rechtsdienst des DVBU. Zudem bemerkte sie, das Baubewilligungsgesuch für das Schwimmbad müsse direkt an die dafür zuständige Gemeindebehörde von Finhaut gerichtet werden ("la requête d'autorisation de construire concernant la piscine doit être adressée directement à l'Administration communale de Finhaut, organe compétent en la matière"). Am 20. Dezember 2004 wurde bei der Gemeinde mit dem offiziellen Formular das Baugesuch zur Erstellung des Schwimmbads (mit Überdeckung, Wärmepumpe und Stützmauer) unterbreitet. Das Gesuch wurde öffentlich aufgelegt und die Gemeinde erteilte am 7. März 2005 die Baubewilligung.
D.
Am 12. Mai 2010 sprach sich die Dienststelle für Strassen- und Flussbau gegen eine Eigentumsübertragung der Parzelle Nr. yyy aus. Auf Aufforderung des Verwaltungs- und Rechtsdienstes des DVBU reichte die Gemeinde am 28. Mai 2010 eine Kopie des Baudossiers des Schwimmbads ein. In der Folge holte die Kantonale Baukommission (KBK) Vormeinungen bei verschiedenen Dienststellen ein.
E.
Am 29. September 2010 eröffnete die KBK A._, die realisierte Baute sei nicht zonenkonform und auch die Standortgebundenheit ausserhalb der Bauzone sei nicht gegeben. Da die Arbeiten ohne Baubewilligung der zuständigen Behörde ausgeführt worden seien, werde der Bauherr aufgefordert, innert der Frist von 3 Monaten den rechtmässigen Zustand wiederherzustellen, indem er das Schwimmbad und die Mauern zurückzubauen habe. Das Grundstück sei wieder der landwirtschaftlichen Nutzung zuzuführen und habe dem natürlichen Geländeverlauf zu entsprechen.
F.
Die von A._ dagegen erhoben Beschwerde wies der Staatsrat am 14. Mai 2014 ab und bestätigte die Wiederherstellungsverfügung. Mit Entscheid vom 6. Februar 2015 wies das Kantonsgericht des Kantons Wallis die Verwaltungsgerichtsbeschwerde ab, soweit es darauf eintrat.
G.
A._ erhebt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt hauptsächlich die Aufhebung des Entscheids des Kantonsgerichts.
Das Kantonsgericht und das Bundesamt für Raumentwicklung (ARE) beantragen die Abweisung der Beschwerde. Der Staatsrat hat auf Vernehmlassung verzichtet. Der Beschwerdeführer hat sich nicht mehr geäussert.

Erwägungen:
1.
1.1. Streitgegenstand bildet die Frage nach der Rechtskonformität der angeordneten Wiederherstellung des rechtmässigen Zustands, nicht dagegen die allfälligen staatshaftungsrechtlichen Forderungen des Beschwerdeführers.
1.2. Angefochten ist ein kantonal letztinstanzlicher Endentscheid über eine öffentlich-rechtliche Angelegenheit (Art. 82 lit. a; Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG). Ein Ausschlussgrund ist nicht gegeben (<ref-law>). Der Beschwerdeführer hat am vorinstanzlichen Verfahren teilgenommen (<ref-law>). Als von der Wiederherstellung Betroffener ist er durch das angefochtene Urteil besonders berührt und hat ein schutzwürdiges Interesse an dessen Aufhebung (Art. 89 Abs. 1 lit. b und c BGG). Er ist daher zur Beschwerdeführung berechtigt. Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
1.3. Mit der Beschwerde kann die Verletzung von Bundesrecht (inkl. Bundesverfassungsrecht) geltend gemacht werden (<ref-law>). Dabei ist in der Beschwerdeschrift in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Bezüglich der Verletzung von verfassungsmässigen Rechten gilt eine qualifizierte Rügepflicht. Das Bundesgericht tritt auf solche Rügen nur ein, wenn sie in der Beschwerde präzise vorgebracht und begründet worden sind (<ref-law> i.V.m. <ref-law>).
2.
2.1. Bauten, die formell und materiell rechtswidrig sind (was hier unbestritten ist), müssen grundsätzlich beseitigt werden. Die Anordnung des Abbruchs bereits erstellter Bauten kann jedoch nach den allgemeinen Prinzipien des Verfassungs- und Verwaltungsrechts (ganz oder teilweise) ausgeschlossen sein. Dies ist insbesondere der Fall, wenn die Wiederherstellung des rechtmässigen Zustands unverhältnismässig wäre. Überdies können unter anderem auch Gründe des Vertrauensschutzes der Wiederherstellung entgegenstehen (vgl. zum Ganzen <ref-ruling> E. 6 S. 364 f. mit Hinweisen).
2.2.
2.2.1. Der Beschwerdeführer rügt zunächst die vorinstanzliche Sachverhaltsfeststellung. Entgegen der Vorinstanz sei dem offiziellen Baugesuchsformular nicht zu entnehmen, dass die KBK für Bauten und Anlagen ausserhalb der Bauzone zuständig sei.
2.2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zu Grunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
2.2.3. Dem offiziellen Baugesuchsformular ist zu entnehmen, dass die Errichtung eines Schwimmbads von der zuständigen Baubewilligungsbehörde genehmigt werden muss (Art. 15 Abs. 1 Baugesetz vom 8. Februar 1996 des Kantons Wallis [BauG; SGS/VS 705.1] i.V.m. Art. 19 Abs. 1 Ziff. 3 lit. i [neu: lit. k] der Bauverordnung vom 2. Oktober 1996 [BauV; SGS/VS 705.100]). Das Baubewilligungsgesuch ist bei der Gemeindebehörde einzureichen (Art. 31 BauV), unabhängig davon, ob die Baute inner- oder ausserhalb der Bauzone erstellt werden soll. Sodann ist in der Baueingabe ausdrücklich um die Erteilung einer Ausnahmebewilligung zu ersuchen und das Ausnahmebegehren zu begründen (Art. 37 Abs. 1 BauV). Das Baugesuchsformular enthält zudem eine Rubrik, in der die Gemeinde einzutragen hat, ob und gegebenenfalls wann sie das Gesuch an das Sekretariat der KBK weitergeleitet hat.
2.2.4. Es ist dem Beschwerdeführer zuzustimmen, dass die Abgrenzung der Zuständigkeiten zwischen dem Gemeinderat (Art. 2 Abs. 1 Ziff. 1 BauG) und der KBK (Art. 2 Abs. 1 Ziff. 2 BauG) im offiziellen Baugesuchsformular keine Erwähnung findet und auch auf die einschlägigen Bestimmungen im Baugesetz nicht verwiesen wird. In dieser Hinsicht erweist sich die Aussage der Vorinstanz, wonach der Beschwerdeführer aus den im Formular aufgeführten Bestimmungen "unschwer" hätte erkennen können, dass für die Erstellung eines Schwimmbads im Freien die Bewilligung einer kantonalen Behörde oder zumindest das Einverständnis einer kantonalen Behörde erforderlich gewesen wäre, als unzutreffend. Der Beschwerdeschrift ist jedoch nicht zu entnehmen (und es ist auch nicht ersichtlich), inwiefern dieser Befund für den Ausgang des vorliegenden Verfahrens entscheidend sein soll, zumal die Vorinstanz noch weitere, wesentlich gewichtigere Gründe anführt, die für die Wiederherstellung des rechtmässigen Zustands sprechen. Dies ist im Folgenden darzulegen.
2.3.
2.3.1. Der in <ref-law> verankerte Grundsatz von Treu und Glauben verleiht einer Person unter anderem einen Anspruch auf Schutz des berechtigten Vertrauens in behördliche Zusicherungen oder sonstiges, bestimmte Erwartungen begründendes Verhalten der Behörden. Voraussetzung für eine Berufung auf den Vertrauensschutz ist, dass die betroffene Person sich berechtigterweise auf die Vertrauensgrundlage verlassen durfte und gestützt darauf nachteilige Dispositionen getroffen hat, die sie nicht mehr rückgängig machen kann. Selbst wenn diese Voraussetzungen erfüllt sind, bleibt eine Interessenabwägung im Einzelfall vorbehalten. Die Berufung auf Treu und Glauben scheitert sodann, wenn ihr überwiegende öffentliche Interessen entgegenstehen (<ref-ruling> E. 2.5.1 S. 72 f.; <ref-ruling> E. 6.1 S. 636 f.; <ref-ruling> E. 4.1 S. 170; je mit Hinweisen).
2.3.2. Der Beschwerdeführer beruft sich ausschliesslich auf seinen guten Glauben. Er bringt vor, er habe, wie vom Kanton verlangt, das Baugesuch für die Erstellung des Schwimmbads bei der Gemeinde eingereicht. Diese habe in der Folge die Baubewilligung erteilt, statt das Gesuch an die für Bauten ausserhalb der Bauzone zuständige KBK weiterzuleiten. Er, der Beschwerdeführer, und die Landschaftsgärtnerei hätten nicht gewusst, dass die Gemeinde verpflichtet gewesen wäre, eine Bewilligung vom Kanton einzuholen. Es könne ihm als Durchschnittsbürger nicht zugemutet werden, die verwaltungsinterne Zuständigkeitsordnung bis in ihre Einzelheiten zu kennen. Er habe gutgläubig angenommen, die von ihm ausgeübte Nutzung stehe in Einklang mit der Baubewilligung, weshalb die Wiederherstellung des rechtmässigen Zustands unterbleiben müsse.
2.3.3. Entgegen seiner Auffassung kann der Beschwerdeführer jedoch nicht als gutgläubig gelten. Wie die Vorinstanz zu Recht ausführt, weichen die vom Beschwerdeführer erstellten Bauten (Schwimmbad mit Überdeckung, Wärmepumpe und Stützmauer) nicht bloss in unbedeutender Weise vom Erlaubten ab, sondern widersprechen dem Raumplanungsrecht in ganz grundlegender Weise. Der Grundsatz der Trennung von Bau- und Nichtbaugebiet stellt eines der wichtigsten Ziele des Raumplanungsrechts dar (Art. 1 Abs. 1 RPG). Die Errichtung von zonenfremden und nicht standortgebundenen Bauten ausserhalb der Bauzonen soll verhindert werden (Art. 24 RPG). Dieser fundamentale Grundsatz des Raumplanungsrechts dürfte heute jedem Bauwilligen bekannt sein (vgl. URS BEELER, Die widerrechtliche Baute, Zürich 1984, S. 84). Jedenfalls kann sich der Beschwerdeführer, dessen Chalet sich ebenfalls in der Landwirtschaftszone befindet und der die damit verbundenen Einschränkungen für die bauliche Nutzung zumindest in groben Zügen kennen musste, bereits aus diesem Grund nicht auf den Vertrauensschutz berufen. Sodann teilte die Gemeinde dem Beschwerdeführer am 8. September 2004 (sechs Tage nach der Einreichung des Baugesuchs) eigens mit, dass er für die Errichtung des Schwimmbads eine Ausnahmebewilligung nach Art. 24 RPG benötige. Trotz dieser Auskunft hat der Beschwerdeführer bei der Gemeinde nachträglich kein modifiziertes Baugesuch eingereicht, um die erforderliche Ausnahmebewilligung zu erhalten; vielmehr liess er die bereits begonnenen Bauarbeiten in der Landwirtschaftszone und auf kantonalem Grund fortsetzen. Dabei hätte ihn der weitere Umstand, dass er zum Teil auf fremden Boden baute, noch zu besonderer Vorsicht bzw. Absicherung veranlassen müssen.
Im Übrigen wurde der Beschwerdeführer, wie den Akten zu entnehmen ist, bereits im Zusammenhang mit der Baubewilligung zur Erstellung des Parkplatzes von der Gemeinde ausdrücklich darauf hingewiesen, dass die kommunale Baubewilligung die weiteren Entscheide der zuständigen Behörden in Bezug auf die Baubewilligung und die Nutzung des kantonalen Boden nicht präjudiziere (vgl. Schreiben vom 18. November 2003; Bst. A hiervor). Daraus konnte er ohne Weiteres ableiten, dass die Existenzberechtigung auch des Schwimmbads raumplanungs-, bau- und eigentumsrechtlich noch nicht abgesichert war und allenfalls noch weitere Bewilligungen einzuholen gewesen wären. Dass er sich in der Folge nicht darum bemühte, sondern die Baute auf eigenes Risiko erstellte, hat er selber zu verantworten.
Ebensowenig kann der Beschwerdeführer aus der Aussage des DVBU, wonach das Baubewilligungsgesuch für das Schwimmbad direkt an die dafür zuständige Gemeindebehörde zu richten sei (vgl. Bst. C hiervor), eine Vertrauensposition ableiten. Nach den einschlägigen kantonalrechtlichen Bestimmungen sind sämtliche Baubewilligungsgesuche zunächst bei der Gemeindebehörde einzureichen (E. 2.2.3). Damit erwies sich die Information des DVBU als korrekt. Auf den Gutglaubensschutz kann sich der Beschwerdeführer daher nicht berufen.
2.4. Vorliegend stehen zudem überwiegende öffentliche Interessen dem Weiterbestand der Baute entgegen. Werden illegal errichtete, dem RPG widersprechende Bauten nicht beseitigt, sondern auf unabsehbare Zeit geduldet, so wird der Grundsatz der Trennung von Bau- und Nichtbaugebiet in Frage gestellt und rechtswidriges Verhalten belohnt. Der Anordnung der Wiederherstellung des rechtmässigen Zustands kommt daher massgebendes Gewicht für den ordnungsgemässen Vollzug des Raumplanungsrechts zu. In Anbetracht der Gesetzesverletzung ist das öffentliche Interesse an der Wiederherstellung des rechtmässigen Zustands entsprechend gross.
3.
Die Beschwerde erweist sich nach dem Ausgeführten als unbegründet und ist abzuweisen. Die von der KBK in der Wiederherstellungsverfügung festgesetzte Frist von drei Monaten zur Wiederherstellung des rechtmässigen Zustands beginnt mit Ergehen dieses Urteils zu laufen. Sollten winterliche Verhältnisse die Wiederherstellungsarbeiten verhindern, müsste der Beschwerdeführer bei der KBK um Gewährung einer Fristverlängerung ersuchen.
Bei diesem Verfahrensausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Den in ihrem amtlichen Wirkungskreis obsiegenden Behörden steht keine Parteientschädigung zu (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000-- werden dem Beschwerdeführer auferlegt.
3.
Es wird keine Parteientschädigung zugesprochen.
4.
Dieses Urteil wird dem Beschwerdeführer, der Einwohnergemeinde Finhaut, dem Staatsrat des Kantons Wallis, dem Kantonsgericht Wallis, Öffentlichrechtliche Abteilung, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 13. November 2015
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Misic