Sachverhalt:
A.
Aufgrund einer Information der Dienststelle für Umweltschutz über die Lagerung von grösseren Mengen mineralischer Bauabfälle am Standort der A._ AG, Bauunternehmung in X._ (Gemeinde Saas-Balen), verfügte die kantonale Baukommission des Kantons Wallis (KBK) am 11. September 2013 die sofortige Arbeitseinstellung.
B.
Am 5. Dezember 2013 verfügte die KBK, die A._ AG, B._ und C._ hätten auf den Parzellen Nrn. 2546, 2553, 2553', 2553c, Blatt Nr. 21, im Orte genannt "Y._" auf dem Gebiet der Gemeinde Saas-Balen, den rechtmässigen Zustand wiederherzustellen, indem sie die aus Containern bestehende Baute komplett abbrechen, die Inertstoffe und den Aushub (soweit noch vorhanden) umweltgerecht entsorgen und sämtliche Baumaterialien, Container usw. entfernen. Das Gelände sei wieder so herzustellen, dass es dem natürlichen Geländeverlauf entspreche. Die Pflanzendecke sei wieder herzustellen und die Grundstücke seien wieder ihrer ursprünglichen landwirtschaftlichen Nutzung zuzuführen.
C.
Dagegen erhoben die A._ AG sowie B._ und C._ am 8. Januar 2014 Beschwerde beim Staatsrat des Kantons Wallis. Dieser führte am 13. Oktober 2014 eine Ortsschau durch. Das Beschwerdeverfahren wurde im Hinblick auf eine angestrebte Zonenplanrevision der Gemeinde Saas-Balen sistiert und im Herbst 2017 wieder aufgenommen. Am 21. Februar 2018 wies der Staatsrat die Beschwerde ab.
Das Kantonsgericht Wallis wies die dagegen gerichtete Beschwerde der A._ AG sowie von B._ und C._ am 23. November 2018 ab und verpflichtete diese, bis zum 31. Juli 2019 auf den Grundstücken Nr. 2546 (GBV Nr. 1443+1466), Nr. 2553 (GBV Nr. 1417), Nr. 2553' (GBV Nr. 1416) und Nr. 2553c (GBV Nr. 1415), Plan Nr. 21 (GBV Plan Nr. 8), den rechtmässigen Zustand wiederherzustellen; insbesondere seien sämtliche Bauten komplett abzubrechen.
D.
Dagegen haben die A._ AG sowie B._ und C._ am 14. Januar 2019 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht erhoben (Verfahren 1C_22/2019). Sie beantragen, der angefochtene Entscheid sei aufzuheben; eventualiter sei die Sache zur Ergänzung der Akten und erneuter Prüfung und Entscheidung an die Vorinstanz zurückzuweisen. Sie berufen sich insbesondere auf eine von der Gemeinde nachträglich aufgefundene Baubewilligung vom 18. September 1967, von der sie erstmals am 31. Dezember 2018 Kenntnis erhalten hätten.
Das Kantonsgericht, der Staatsrat und die KBK beantragen, die Beschwerde sei abzuweisen. Auch das Bundesamt für Raumentwicklung (ARE) schliesst auf Abweisung der Beschwerde. Die Einwohnergemeinde Saas-Balen hat sich nicht geäussert.
Die Beschwerdeführer halten mit Replik vom 7. März 2019 an ihren Anträgen fest.
Mit Verfügung vom 11. Februar 2019 wurde der Beschwerde aufschiebende Wirkung zuerkannt.
E.
Am 1. April 2019 stellten die A._ AG sowie B._ und C._ unter Berufung auf die nachträglich aufgefundene Baubewilligung ein Revisionsgesuch beim Kantonsgericht Wallis gegen dessen Urteil vom 23. November 2018. Am 12. August 2019 wies das Kantonsgericht das Revisionsgesuch ab.
Gegen den Revisionsentscheid vom 12. August 2019 haben die A._ AG sowie B._ und C._ am 16. September 2019 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht erhoben (Verfahren 1C_476/2019). Sie beantragen, der angefochtene Entscheid sei aufzuheben und die Vorinstanz sei in Gutheissung des Revisionsgesuchs anzuweisen, das Verfahren A1 18 68 unter Einbezug der nicht berücksichtigten Baubewilligung vom 18. September 1967 wieder aufzunehmen und einen neuen Sachentscheid zu fällen.
Das Kantonsgericht und der Staatsrat schliessen auf Abweisung der Beschwerde. Die KBK hat auf eine Stellungnahme verzichtet. Die Einwohnergemeinde Saas-Balen unterstützt das Begehren der Beschwerdeführer.
F.
Das bundesgerichtliche Verfahren 1C_22/2019 wurde bis zum Entscheid des Kantonsgerichts über das Revisionsgesuch sistiert und anschliessend wieder aufgenommen.
Am 22. Oktober 2019 (mit Ergänzung vom 23. Dezember 2019) äusserte sich das Bundesamt für Umwelt (BAFU) zu den umweltrechtlichen Aspekten der Beschwerden. Gemäss Auskunft des Kantons sei der Gewässerraum von der Gemeinde Saas-Balen am 2. April 2017 eigentümerverbindlich festgelegt und vom Staatsrat am 20. Juni 2018 genehmigt und homologiert worden. Die im Gewässerraum liegenden Bauten und Anlagen verfügten (mit Ausnahme des bewilligten Werkstattgebäudes) nicht über eine Baubewilligung und seien daher nicht in ihrem Bestand im Gewässerraum geschützt. Überdies bedürfe die Ablagerung von Aushub-, Abbruch- und Abraummaterial einer Deponieerrichtungs- und -betriebsbewilligung sowie einer gewässerschutzrechtlichen Genehmigung nach <ref-law> (SR 814.20), andernfalls sie als unzulässig zu beurteilen sei.
Die Beschwerdeführer nahmen am 3. Februar 2020 zu den Vernehmlassungen der Bundesämter und der Vorinstanzen Stellung. Sie beantragen die Vornahme eines Augenscheins
G. Mit Verfügung vom 28. Oktober 2019 wurden die Verfahren 1C_22/2019 und 1C_476/2019 vereinigt. Das Gesuch um Gewährung der aufschiebenden Wirkung im Verfahren 1C_476/2019 wurde abgewiesen und der Umfang der aufschiebenden Wirkung im Verfahren 1C_22/2019 präzisiert.

Erwägungen:
1.
Gegen beide kantonal letztinstanzlichen Endentscheide des Kantonsgerichts steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen (Art. 82 lit. a, 86 Abs. 1 lit. d und 90 BGG).
1.1. Die Beschwerdeführer sind als Eigentümer der Parzellen und Betreiber der Anlagen, die Gegenstand der Wiederherstellungsverfügung sind, zur Beschwerde befugt (<ref-law>), und zwar sowohl gegen den kantonalen Beschwerdeentscheid (im Verfahren 1C_22/2019) als auch gegen den in dieser Sache ergangenen Revisionsentscheid des Kantonsgerichts (im Verfahren 1C_476/2019).
Da die übrigen Sachurteilsvoraussetzungen vorliegen, ist auf die rechtzeitig erhobenen Beschwerden grundsätzlich einzutreten, vorbehältlich nicht rechtsgenügend begründeter Rügen (unten E. 2).
2.
Das Bundesgericht prüft die Verletzung von Grundrechten, insbesondere die willkürliche Anwendung von kantonalem Recht, nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und genügend begründet worden ist (<ref-law>; <ref-ruling> E. 1.4.2 S. 254 mit Hinweisen). Stützt sich der angefochtene Entscheid auf mehrere alternative Begründungen, muss jede dieser Begründungen rechtsgenügend angefochten werden. Ob diese Anforderungen vorliegend erfüllt sind, wird im jeweiligen Zusammenhang näher zu prüfen sein.
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat, sofern dieser nicht offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 105 und Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel können nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>; vgl. dazu unten E. 6.2).
Wie im Folgenden darzulegen sein wird, genügen die Sachverhaltsfeststellungen der Vorinstanz zur Beurteilung des Streitfalls; auf den von den Beschwerdeführern im Verfahren 1C_22/2019 beantragten Augenschein kann verzichtet werden.
3.
Zunächst ist die Beschwerde gegen den Revisionsentscheid zu prüfen.
3.1. Dieser stützt sich auf kantonales Verfahrensrecht: Art. 81 des Walliser Gesetzes über das Verwaltungsverfahren und die Verwaltungsrechtspflege vom 6. Oktober 1976 [VVRG; SGS 172.6] verweist auf die Bestimmungen der ZPO; diese gelten jedoch nur kraft Verweises, d.h. als kantonales Recht.
Dessen Auslegung und Anwendung kann vom Bundesgericht grundsätzlich nur unter dem Blickwinkel des Willkürverbots überprüft werden. Willkür liegt nach der Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder sogar vorzuziehen wäre. Das Bundesgericht weicht vom Entscheid der kantonalen Instanz nur ab, wenn dieser offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2.2.2 S. 318 f. mit Hinweisen).
3.2. Die Beschwerdeführer hatten die Revision des Beschwerdeentscheids gestützt auf eine nachträglich von der Gemeinde aufgefundene Baubewilligung der KBK vom 18. September 1967 für eine Baute auf Parzelle Nr. 2546 verlangt. Sie machten geltend, diese sei für den Ausgang des Rechtsstreits erheblich, weil bisher sämtliche kantonalen Instanzen davon ausgegangen seien, dass die zu beseitigenden Bauten und Anlagen ohne Bewilligung, d.h. formell rechtswidrig, erstellt worden seien.
3.3. In seinem Revisionsentscheid stellte das Kantonsgericht einleitend klar, dass sich der Wiederherstellungsbefehl gemäss Dispositiv des Beschwerdeentscheids vom 23. November 2018 auf sämtliche Bauten auf den Parzellen der Beschwerdeführer beziehe, d.h. auch der Abbruch der angeblich bewilligten Baute auf Parzelle Nr. 2546 Streitgegenstand gewesen sei. Es verneinte jedoch das Vorliegen eines Revisionsgrundes mit verschiedenen alternativen Begründungen:
- Zum einen gehe aus der eingereichten Baubewilligung allein (ohne die Baupläne) weder hervor, auf welchem Grundstück die Baute bewilligt worden sei, noch ob die in der Baubewilligung enthaltenen Vorbehalte und Bedingungen der KBK eingehalten worden seien.
- Zum anderen könne ausgeschlossen werden, dass die damals bewilligte Baute den heute bestehenden Bauten entspreche. Nach eigenen Angaben der Beschwerdeführer seien auf Parzelle Nr. 2553 ausser der Betonwand Süd alle Teile (Boden, Wände, Dach) abgebrochen und neu erstellt worden; auch am Gebäude auf Grundstück Nr. 2546 seien um 1993 Arbeiten ausgeführt worden, weil dieses beim Unwetter von 1993 schwer beschädigt worden sei. Die ursprünglichen Bauten bestünden daher nicht mehr, und für die Um- und Wiederaufbauten seien keine Baubewilligungen eingeholt oder vorgelegt worden.
- Schliesslich hätten die Beschwerdeführer schon im Beschwerdeverfahren auf die Existenz einer Baubewilligung hinweisen und deren Edition verlangen können. Aus ihrer schriftlichen Anfrage bei der Gemeinde vom 21. Dezember 2018 gehe nämlich klar hervor, dass sie nicht nach der Existenz einer Baubewilligung gefragt, sondern um die Kopie einer Baubewilligung ersucht hätten, die ihnen bereits seit Längerem bekannt gewesen sei.
4.
Im Folgenden sind zunächst die formellen Rügen zu prüfen.
4.1. Die Beschwerdeführer rügen eine Verletzung des rechtlichen Gehörs, weil das Kantonsgericht einleitend den Umfang des Wiederherstellungsbefehls geprüft habe; dies stelle faktisch eine Erläuterung des Entscheids vom 23. November 2018 dar, die von den Beschwerdeführern weder beantragt noch veranlasst worden sei. Eine Erläuterung von Amtes wegen sei gemäss <ref-law> zwar zulässig; hierzu müssten die Parteien jedoch vorgängig angehört werden, was vorliegend nicht geschehen sei.
Dem ist entgegenzuhalten, dass das Kantonsgericht die Erheblichkeit des von den Beschwerdeführern geltend gemachten Revisionsgrunds (Baubewilligung) für den in Revision gezogenen Entscheid prüfen musste. Dafür musste es feststellen, ob die angeblich bewilligte Baute vom Wiederherstellungsbefehl umfasst war oder nicht, was eine Auslegung des Urteilsdispositivs vom 23. November 2018 bedingte. Dies stellt Teil der Begründung des Revisionsentscheids dar und keine selbstständige Urteilserläuterung i.S.v. <ref-law>. Die Beschwerdeführer konnten (und mussten) sich schon in der Begründung ihres Revisionsgesuchs zur Erheblichkeit des Revisionsgrunds äussern (<ref-law>), weshalb kein Anlass bestand, sie nochmals zu dieser Frage anzuhören.
4.2. Soweit die Beschwerdeführer rügen, das Revisionsgesuch sei zu Unrecht als "offensichtlich unbegründet" eingestuft und deshalb der Gegenseite nicht zur Stellungnahme unterbreitet worden (<ref-law>), ist nicht ersichtlich, inwiefern ihnen dies zum Nachteil gereichte.
4.3. Die Beschwerdeführer rügen schliesslich eine Verletzung des rechtlichen Gehörs und der Untersuchungsmaxime. Das Kantonsgericht habe die Baubewilligung ohne das Baudossier für nicht aussagekräftig erachtet. Unter diesen Umständen wäre es verpflichtet gewesen, die nötigen Abklärungen selbst zu treffen, d.h. das Baudossier beizuziehen, oder die Beschwerdeführer zumindest auf dessen Erheblichkeit hinzuweisen, d.h. ihnen Gelegenheit zu geben, dieses einzureichen.
Für Revisionsgesuche als ausserordentliche Rechtsmittel gelten jedoch strenge Begründungsanforderungen: Die Gesuchsteller sind verpflichtet, das Vorliegen aller Revisionsvoraussetzungen darzulegen und, sofern möglich, zu belegen. Die Beschwerdeführer waren bei Einreichung ihres Revisionsgesuchs am 1. April 2019 bereits im Besitz des Baudossiers, das ihnen am 28. Januar 2019 von der KBK in Kopie übermittelt worden war (vgl. Stellungnahmen der KBK vom 7. Februar 2019 und der Beschwerdeführer vom 7. März 2019). Wenn sie ihr Revisionsgesuch dennoch einzig auf die Baubewilligung stützten und bewusst darauf verzichteten, das Baudossier mit den bewilligten Plänen einzureichen, war das Kantonsgericht berechtigt, seine Prüfung auf die Baubewilligung zu beschränken.
5.
Materiell rügen die Beschwerdeführer eine willkürliche Anwendung von <ref-law> (als kantonales Verfahrensrecht).
5.1. Sie machen geltend, es sei willkürlich anzunehmen, dass die 1967 bewilligte Baute heute nicht mehr bestehe und der rechtmässige Zustand insoweit nicht mehr hergestellt werden könnte. Sie legen dies aber nicht substanziiert dar, sondern beschränken sich auf den Hinweis, dass kein detaillierter Abgleich des 1967 bewilligten und des heutigen Bestandes vorgenommen worden sei. Diese Ausführungen sind zu allgemein gehalten, um Willkür mit Bezug auf die 1967 bewilligte Baute zu belegen. Die Beschwerdeführer sind als Eigentümer der Parzellen und Betreiber bzw. Aktionäre des Bauunternehmens mit den heutigen Verhältnissen bestens vertraut. Auch ohne Vorliegen einer detaillierten Bestandesaufnahme wären sie daher in der Lage und gehalten gewesen vor Bundesgericht darzulegen, inwiefern die 1967 bewilligte Baute heute noch besteht.
5.2. Ungenügend ist auch die Auseinandersetzung mit der weiteren Begründung des Kantonsgerichts: Die Beschwerdeführer machen geltend, sie hätten erst aus dem Urteil vom 23. November 2018 erfahren, dass schon in den 60er Jahren im Wallis eine Baubewilligungspflicht bestand. Sie setzen sich aber nicht mit dem Hauptargument des Kantonsgerichts auseinander, wonach sich aus ihrem Schreiben an die Gemeinde vom 21. Dezember 2018 klar ergebe, dass sie schon seit geraumer Zeit Kenntnis von der Existenz der Baubewilligung hatten.
5.3. Auf die Beschwerde kann daher in diesen Punkten mangels genügender Begründung nicht eingetreten werden; im Übrigen (hinsichtlich der formellen Rügen) ist sie abzuweisen.
6.
Zu prüfen ist noch die Beschwerde gegen den Entscheid vom 23. November 2018.
6.1. Das Kantonsgericht hielt fest, die fraglichen Bauten und Materialdepots lägen ausserhalb der Bauzone, im Gewässerraum der Saaser Vispa. Sie seien ohne Bewilligung erstellt und erneuert worden; auch für die Nutzung der Grundstücke als Materialdepot liege keine Bewilligung vor. Sie seien daher nicht rechtmässig erstellt worden und genössen schon aus diesem Grund keinen Besitzstandsschutz nach Art. 24c Abs. 1 RPG (SR 700) oder Art. 37a RPG. Im Übrigen seien die Bauten und das Materialdepot über die Jahre erneuert und erheblich erweitert worden und könnten keinesfalls mit dem Zustand von vor 20 oder 30 Jahren verglichen werden. Insofern könnten die Erneuerungen und Änderungen der Bauten und des Materialdepots selbst dann nicht nachträglich bewilligt werden, wenn sie rechtmässig erstellt worden wären.
6.2. Die Beschwerdeführer bestreiten in erster Linie, dass die Bauten und Anlagen formell rechtswidrig erstellt worden seien; sie berufen sich hierfür auf die nachträglich aufgefundene Baubewilligung.
Fraglich ist, ob es sich dabei um ein zulässiges Novum i.S.v. <ref-law> handelt. Dies würde voraussetzen, dass erst der angefochtene Entscheid des Kantonsgerichts Anlass für eine schriftliche Anfrage bei der Gemeinde nach dem Vorliegen einer Baubewilligung gab.
6.2.1. Dies ist grundsätzlich zu verneinen: Die Argumentation der Beschwerdeführer, wonach sie erst aufgrund der Lektüre des kantonsgerichtlichen Entscheids vom 23. November 2018 erfahren hätten, dass schon in den 60er Jahren im Kanton Wallis eine Baubewilligung erforderlich gewesen sei, und deshalb erstmals Anlass hatten, sich schriftlich bei der Gemeinde nach dem Vorliegen einer Baubewilligung zu erkundigen, steht im Widerspruch zum Wortlaut ihres Schreibens vom 21. Dezember 2018, wo sie um die Kopie einer ganz bestimmten Baubewilligung (Lagerraum/Einstellhalle auf Parzelle GBV Nr. 1443 aus der Mitte der 60er Jahre) bitten, von der sie mündlich vom 1990 verstorbenen D._ erfahren hätten, weil sie die Baubewilligung in ihren Erbunterlagen nicht mehr gefunden hätten. Wussten die Beschwerdeführer daher von der Existenz dieser Baubewilligung, hätten sie schon früher Anlass gehabt, dies vorzubringen und deren Edition zu beantragen. Der Nachweis, dass eine Baute einst bewilligt worden ist, obliegt grundsätzlich der Bauherrschaft; diese trägt auch die Folgen einer allfälligen Beweislosigkeit (ZAUGG/LUDWIG, Baugesetz des Kantons Bern, Kommentar Bd. I, 4. Aufl., Art. 3 Rz. 2).
6.2.2. Allerdings ist den Beschwerdeführern einzuräumen, dass die KBK verpflichtet gewesen wäre, die Baubewilligung und das Baudossier, die sich in ihrem Archiv befanden, von Amtes wegen zu edieren. Dies gilt selbst dann, wenn sie ursprünglich der Auffassung war, die Baubewilligung für ein Garagen-Werkstattgebäude auf Parzelle Nr. 2546 sei nicht entscheiderheblich, weil sich der Wiederherstellungsbefehl nicht auf diese Baute beziehe (so Stellungnahme der KBK vom 7. Februar 2019), wurde doch der Abbruch der Baute auf Parzelle Nr. 2546 spätestens im Rechtsmittelverfahren thematisiert (vgl. dazu Revisionsentscheid, E. 2.4.2 bis E. 2.4.5). Ob die nachträglich aufgefundene Baubewilligung (samt dem von der KBK eingereichten Baudossier) deshalb zugelassen werden muss, um ein faires Verfahren zu gewährleisten (<ref-law>; Art. 6 Ziff. 1 EMRK), kann offenbleiben, weil die Baubewilligung nicht entscheiderheblich ist:
6.3. Wie im Folgenden aufzuzeigen sein wird, ist die bewilligte Baute nicht mehr vorhanden (unten E. 7) und die an ihrer Stelle errichtete Baute wurde weder bewilligt noch kann sie nachträglich bewilligt werden (unten E. 8-10). Für die Baute auf Parzelle Nr. 2553 wie auch für die Materialdepots liegt ohnehin keine Baubewilligung vor (vgl. dazu unten E. 11 und 12).
7.
Die KBK erteilte am 18. September 1967 die Bewilligung für eine "Garage mit Werkräumen" auf Parzelle Nr. 2546. Gemäss Baugesuch bestand diese aus einem Kellergeschoss aus Zementsteinen (20 cm) und einem Garagenaufbau aus Holz; als Bedachung wurden Natursteinplatten vorgeschrieben. Gemäss den genehmigten Bauplänen betrug der Grundriss 12 x 4 m.
Das Kantonsgericht stellte fest, alle Bauten seien über die Jahre erneuert und erheblich erweitert worden; die ursprüngliche Bausubstanz sei aufgrund der regen Bautätigkeit nicht mehr vorhanden bzw. in ihrer Identität nicht gewahrt. Speziell zur Baute auf Parzelle Nr. 2546 hielt es fest, diese bestehe heute aus Containern sowie Betonwänden; letztere seien um 1993 ausgeführt worden.
Die Beschwerdeführer bestreiten dies pauschal, zeigen aber nicht substanziiert auf, inwiefern die Feststellungen des Kantonsgerichts offensichtlich unrichtig sind. Dies ist auch nicht ersichtlich, hatten die Beschwerdeführer doch in ihrer Beschwerde an das Kantonsgericht selbst dargelegt, dass die Baute saniert werden musste, nachdem sie beim Unwetter von 1993 schwer beschädigt worden sei. Den Fortbestand einer Holzgarage haben sie (mit Stellungnahme vom 7. März 2019) ausdrücklich bestritten.
Unter diesen Umständen ist das Bundesgericht an den vom Kantonsgericht festgestellten Sachverhalt gebunden (<ref-law>). Danach ist von der 1967 bewilligten Holzgarage mit einem Untergeschoss aus Zementsteinen und einem Dach aus Natursteinplatten auf Parzelle Nr. 2546 nichts mehr vorhanden.
8.
Die ursprüngliche Baute (Garage mit Werkräumen) wurde 1967 bewilligt, vor Inkrafttreten des Eidgenössischen Gewässerschutzgesetzes vom 8. Oktober 1971 am 1. Juli 1972, welches erstmals die Trennung der Bauzonen von den Nichtbauzonen vorsah. Es handelte sich somit um eine altrechtliche Baute i.S.v. Art. 41 Abs. 1 der Raumplanungsverordnung vom 28. Juni 2000 (RPV; SR 700.1). Die ursprüngliche Bausubstanz wurde 1993 vollständig ersetzt, weshalb rechtlich von einem Wiederaufbau auszugehen ist. Dieser Wiederaufbau erfolgte ohne eine Baubewilligung, d.h. die heute vorhandene Baute ist formell rechtswidrig. Zu prüfen ist deshalb, ob sie nachträglich bewilligt werden kann.
Vorab stellt sich die Frage nach dem anwendbaren Recht.
8.1. Bei der Prüfung der Bewilligungsfähigkeit von ohne Bewilligung erstellten oder geänderten Bauten erachtet das Bundesgericht in der Regel den Rechtszustand im Zeitpunkt der Errichtung der Baute als massgeblich, es sei denn die Baute könne nach dem im Zeitpunkt des Entscheids geltenden "milderen" Rechts bewilligt werden (<ref-ruling> E. 252 E. 3a/bb S. 252; <ref-ruling> E. 4 S. 69; vgl. auch Urteil 1C_311/2012 vom 28. August 2013 E. 5.3 und 5.4, in: ZBl 115/2014 207). Auf strengeres neues Recht wird nur abgestellt, wenn der Bauherr bewusst keine Bewilligung eingeholt hat, weil er wusste, dass vor der Erteilung der Bewilligung neues strengeres Recht in Kraft treten werde (<ref-ruling> E. 5c S. 304; zum Ganzen vgl. BERNHARD WALDMANN, in: Fachhandbuch Baurecht, Rz. 6.9 S. 583 f.; KONRAD WILLI, Die Besitzstandsgarantie für vorschriftswidrige Bauten und Anlagen innerhalb der Bauzone, Diss. Zürich 2003, S. 22 ff.; vgl. zur analogen Frage im Rahmen von Art. 24c RPG und <ref-law> unten E. 11.3).
Diese, der Grundregel des intertemporalen Rechts - wonach die erstinstanzlich entscheidende Behörde das zur Zeit ihres Entscheids geltende Recht anwendet (vgl. z.B. <ref-ruling> E. 11.1 S. 260; <ref-ruling> E. 5e/aa S. 598 mit Hinweisen) - widersprechende Praxis wirft zahlreiche praktische Probleme auf (z.B. fehlende Dokumentation des Ausgangszustands bei geänderten Bauten; Schwierigkeit der Feststellungen weit zurückliegenden kantonalen und kommunalen Rechts). Wer keine Baubewilligung eingeholt hat, kann nicht in jedem Fall auf den Schutz der von ihm getätigten Investitionen im Falle einer Rechtsänderung vertrauen.
8.2. Jedenfalls aber kann die zitierte Praxis nicht auf Rechtsvorschriften angewendet werden, die zur Durchsetzung erheblicher öffentlicher Interessen erlassen worden sind. Solche Bestimmungen sind zwingend anzuwenden, auch wenn sie erst im Lauf eines Rechtsmittelverfahrens in Kraft treten (BGE <ref-ruling> E. 5e/aa S. 598 mit Hinweisen), und müssen daher erst recht bei der erstmaligen (nachträglichen) Bewilligung einer formell rechtswidrigen Baute zur Anwendung kommen. Zwingende Gründe für eine sofortige Anwendung neuen Rechts hat das Bundesgericht im Bereich des Gewässer-, Natur-, Heimat- und Umweltschutzrechts als gegeben erachtet (<ref-ruling> E. 2.3 S. 390).
Dazu gehören namentlich die am 1. Juni 2011 in Kraft getretenen neuen Bestimmungen der Gewässerschutzverordnung (GSchV; SR 814.201) über den Gewässerraum (vgl. <ref-ruling> E. 4.2 S. 480 f.; Urteil 1C_505/2011 vom 1. Februar 2012 E. 3.1, in: URP 2012 160; RDAF 2013 I 483). Bauten im Gewässerraum, die vor dem Stichtag (1. Juni 2011) ohne Baubewilligung errichtet oder geändert wurden, sind somit in ihrem Bestand nur geschützt, wenn sie auch heute noch im Gewässerraum bewilligt werden könnten. Art. 41c Abs. 2 GSchV, wonach Anlagen im Gewässerraum in ihrem Bestand grundsätzlich geschützt sind, sofern sie rechtmässig erstellt wurden und bestimmungsgemäss nutzbar sind, umfasst somit nur formell rechtmässige, d.h. rechtskräftig bewilligte Bauten und Anlagen (so auch das BAFU in seiner Vernehmlassung; a.A. NINA MASSÜGER SÁNCHEZ SANDOVAL, Bestandesschutz von Bauten und Anlagen innerhalb des Gewässerraums im Kanton Zürich, PBG aktuell 4/2012, S. 8 oben).
9.
Parzelle Nr. 2546 befindet sich heute vollständig im Gewässerraum der Saaser Vispa, in dem nur standortgebundene, im öffentlichen Interesse liegende Anlagen erstellt werden dürfen (Art. 41c Abs. 1 GSchV). Bestehende Bauten und Anlagen sind gemäss Art. 41c Abs. 2 GSchV in ihrem Bestand grundsätzlich geschützt, sofern sie rechtmässig erstellt wurden und bestimmungsgemäss nutzbar sind.
9.1. In Literatur und Rechtsprechung ist streitig, ob Art. 41c Abs. 2 GSchV bei zonenwidrigen Bauten ausserhalb der Bauzone eigenständige Bedeutung zukommt, oder ob sich der Besitzstandsschutz für diese Kategorie von Bauten nach Art. 24c RPG richtet.
9.1.1. Letztere Auffassung vertrat das Bundesgericht im Urteil 1C_345/2014 vom 17. Juni 2015 E. 4 (in: URP 2015 706; RDAF, 2016 I 394), gestützt auf eine Äusserung des BAFU (im Erläuternden Bericht vom 20. April 2011 zur Parlamentarischen Initiative Schutz und Nutzung der Gewässer [07.492] - Änderung der Gewässerschutz-, Wasserbau-, Energie- und Fischereiverordnung, S. 15; nachfolgend: Erläuternder Bericht). Es ging davon aus, dass die Belange des Gewässerschutzes im Rahmen der Interessenabwägung nach Art. 24c Abs. 5 RPG und <ref-law> zu berücksichtigen seien.
9.1.2. In der Literatur wird dieser Entscheid kritisiert (CHRISTOPH FRITZSCHE, in: Hettich/Jansen/Norer, Kommentar GSchG/WBG, Art. 36a Rz. 138; CORDELIA BÄHR, Rechtsprechungsbericht, URP 2020 S. 44-49) und die Auffassung vertreten, nach Wortlaut, Systematik und Zweck enthalte Art. 41c Abs. 2 GSchV eine eigenständige Besitzstandsgarantie, die sich am Ziel der Gewährleistung der Gewässerfunktionen i.S.v. <ref-law> sowie an der Eigentumsgarantie (<ref-law>) und dem Vertrauensschutz (<ref-law>) orientiere, d.h. an der verfassungsmässigen Besitzstandsgarantie (BÄHR, a.a.O., S. 4; so auch - jedenfalls für Bauten ausserhalb der Bauzone - HANS W. STUTZ, Uferstreifen und Gewässerraum - Umsetzung durch die Kantone, in URP 2012 S. 103 und MASSÜGER SÁNCHEZ SANDOVAL, a.a.O., PBG aktuell 4/2012 S. 23-25; in diesem Sinne auch verschiedene kantonale Entscheide; vgl. Verwaltungsgericht St. Gallen, Urteil B 2013/153 vom 24. März 2015 E. 5.1; Verwaltungsgericht Bern, Urteile VGE 100.2012. 463 vom 7. Juli 2014 E. 8.4, in: URP 2014 668; VGE 100.2013.134 vom 16. Dezember 2014 E. 7.5.1).
9.2. Die Kritik erscheint berechtigt.
Seinem Wortlaut nach schützt Art. 41c Abs. 2 GSchV altrechtliche Bauten nur "in ihrem Bestand" (wie Art. 24c Abs. 1 RPG), ohne die Änderung, Erweiterung oder den Wiederaufbau zu erwähnen, die nach Art. 24c Abs. 2 RPG gestattet sind, oder auf diese Bestimmung zu verweisen.
Art. 24c RPG erlaubt lediglich Ausnahmen vom Erfordernis der Zonenkonformität. Bauten im Gewässerraum sind aber gewässerschutzrechtlich widerrechtlich, und zwar unabhängig davon, ob sie in der Landwirtschaftszone zonenkonform oder zonenwidrig sind. Dementsprechend fehlt eine raumplanungsrechtliche Regelung für zonenkonforme Bauten im Gewässerraum.
Gegen einen erweiterten Besitzstandsschutz nach Art. 24c Abs. 2 RPG im Gewässerraum spricht der erhöhte Schutz vor Überbauung, den dieser im Vergleich zur Landwirtschaftszone geniesst: Nach Art. 41c Abs. 1 GSchV genügt die Standortgebundenheit in der Landwirtschaftszone nicht, sondern Bauten und Anlagen müssen auf einen Standort im Gewässerraum angewiesen sein (vgl. BAFU, Erläuternder Bericht, S. 14; FRITZSCHE, a.a.O., Art. 36a Rz. 114-116) und im öffentlichen Interesse liegen. Dies belegt das gewichtige öffentliche Interesse an der Freihaltung der Gewässerräume, welche die natürlichen Funktionen der Gewässer (<ref-law>; vgl. dazu <ref-ruling> E. 2.1 S. 430 f.) und die für den Hochwasserschutz notwendige Abflusskapazität gewährleisten (<ref-law> und Art. 3 Abs. 1 und 4 Abs. 2 des Wasserbaugesetzes vom 21. Juni 1991; SR 721.100). Uferbereiche sind überdies als wichtiger Lebensraum für Tiere und Pflanzen sowie als Vernetzungskorridor besonders schutzwürdig (<ref-law>; <ref-law>; vgl. auch <ref-law> zur Ufervegetation). Die Freihaltung der Ufer ist schliesslich Voraussetzungen für eine spätere Revitalisierung der Gewässer (<ref-law>).
Zwar trifft es zu, dass Art. 41c Abs. 2 GSchV den Besitzstandsschutz im Unterschied zu Art. 24c RPG lediglich auf Verordnungsstufe regelt (so Urteil 1C_345/2014 vom 17. Juni 2015 E. 4.1.3, in: URP 2015 706; RDAF, 2016 I 394). Das spricht aber nicht gegen einen restriktiveren Besitzstandsschutz: Es ist grundsätzlich Sache des Gesetzgebers zu entscheiden, ob er auch für die nach <ref-law> geschützten Gewässerraume einen erweiterten Besitzstandsschutz einräumen will. Mangels einer gesetzlichen Regelung gilt nur (aber immerhin) der aus der Eigentumsgarantie und dem Vertrauensschutz abgeleitete verfassungsrechtliche Besitzstandsschutz (so auch Verwaltungsgericht St. Gallen, a.a.O, E. 5.1).
Dieser umfasst den Bestand, die Weiternutzung und den Unterhalt von Bauten. Zulässig dürften - unter Berücksichtigung des Normzwecks und des Verhältnismässigkeitsprinzips - auch Umbauten sein, welche die Funktionen des Gewässerraums nicht berühren, wie die im Entscheid 1C_345/2014 vom 17. Juni 2015 streitige Installation von Solarzellen auf einer bestehenden Baute (diese ist heute nach Art. 18a Abs. 1 RPG in der Regel sogar ohne Baubewilligung zulässig). Dagegen dürfen zonenwidrige Bauten ausserhalb der Bauzone im Gewässerraum weder erweitert noch wiederaufgebaut werden, weil dadurch der gewässerrechtswidrige Zustand verstärkt und über die Lebensdauer der ursprünglich bewilligten Baute hinaus perpetuiert würde. Dies würde das Ziel von <ref-law>, die Gewässerräume zumindest auf längere Sicht von Bauten und Anlagen freizuhalten, vereiteln.
9.3. Zusammenfassend ist festzuhalten, dass der ohne Baubewilligung erfolgte Wiederaufbau der altrechtlichen Baute auf Parzelle Nr. 2546 im Gewässerraum auch nachträglich nicht bewilligt werden kann. Daran ändert der Einwand der Beschwerdeführer nichts, dass die Saaser Vispa heute verbaut ist und die Bauten auf der angrenzenden Parzelle GBV Nr. 1418 einer Revitalisierung zumindest kurzfristig entgegenstehen.
10.
Im Übrigen steht der nachträglichen Bewilligung der Ersatzbaute auf Parzelle Nr. 2546 auch deren Lage in der Gefahrenzone entgegen.
10.1. Die Vorinstanz führte aus, der Standort befinde sich in der roten Lawinengefahrenzone und der roten Hochwassergefahrenzone. Das Gericht verwies auf Art. 31 Abs. 2 des Walliser Gesetzes zur Ausführung des Bundesgesetzes über die Raumplanung vom 23. Januar 1987 (kRPG; SGS/VS 701.1) in der zum Entscheidzeitpunkt geltenden Fassung) dürften in Gefahrenzonen keine Bauvorhaben bewilligt werden, die zu einer Gefährdung von Menschen, Tieren und erheblichen Sachwerten führen; Umbauten und Zweckänderungen bestehender Bauten seien nur gestattet, wenn dadurch das Risiko vermindert werde. Die Dienststelle für Strassen, Verkehr und Flussbau habe in ihrer Vormeinung überdies darauf hingewiesen, dass bei lokalen Erosionen oder einem Hochwasserereignis Material mitgerissen und im Bachbett landen könnte, was zu einer speziellen Gefahrensituation (z.B. Verklausung vor Ort oder flussabwärts) führen könnte.
10.2. Die Beschwerdeführer bestreiten die Hochwassergefahr. Ihnen ist einzuräumen, dass die Parzelle Nr. 2546 - im Gegensatz zu den übrigen Parzellen - nicht vollständig in der roten Gefahrenzone Hochwasser (erhebliche Gefährdung), sondern teilweise in der blauen Zone (mittlere Gefährdung) liegt. Dies ändert allerdings nichts an der Lage der Baute in einer Gefahrenzone. Im Übrigen liegt die Parzelle Nr. 2546 (wie auch alle anderen Parzellen der Beschwerdeführer) vollständig in der roten Zone für Lawinengefahr. Zwar wurden die Gefahrenzonenkarten erst vor kurzem erstellt; es ist jedoch davon auszugehen, dass die in ihnen dargestellten Naturgefahren auch schon früher bestanden.
10.3. Sowohl der zum Zeitpunkt des Wiederaufbaus 1993 geltende aArt. 24 Abs. 2 RPG (AS 1979 II 1573 ff.) als auch der 2013 (zum Zeitpunkt des erstinstanzlichen Entscheids der KBK) geltende Art. 24c RPG lassen einen Wiederaufbau nur zu, wenn er mit wichtigen Anliegen der Raumplanung vereinbar ist; <ref-law> präzisiert, dass ihm keine anderen überwiegenden öffentlichen Interessen entgegenstehen dürfen. Diese Prüfung bedingt eine umfassende Interessenabwägung, vergleichbar derjenigen nach Art. 24 lit. b RPG (Urteil 1C_43/2015 vom 6. November 2015 E. 7.2 mit Hinweisen; RUDOLF MUGGLI, in: Aemisegger/Moor/Ruch/Tschannen, Praxiskommentar RPG: Bauen ausserhalb der Bauzonen, 2017, Art. 24c Rz. 46).
Es ist ein wichtiges Anliegen der Raumplanung, dass keine Bauten erstellt werden, wo wegen drohender Naturgewalten Menschen und erhebliche Sachwerte zu Schaden kommen können (vgl. Urteile 1A.125/2000 vom 23. August 2000 E. 4; 1P.329/2005 vom 27. Juli 2005 E. 3.5, je mit Hinweisen). Dieses spricht gegen den Wiederaufbau der Baute an ihrem bisherigen Standort in der Gefahrenzone für Hochwasser und Lawinen. Dieses öffentliche Interesse überwiegt die privaten Interessen, zumal die 1993 angefallenen Investitionskosten gering gewesen sein dürften (Eigenbau) und längst amortisiert sind. Im Übrigen widerspricht der Wiederaufbau auch den in Art. 41c Abs. 1 und 2 GSchV konkretisierten Interessen an der Freihaltung des Gewässerraums (vgl. oben E. 9).
11.
Zu prüfen ist noch die weitere Baute auf Parzelle Nr. 2553 (GBV Nr. 1417).
11.1. Die Beschwerdeführer machen geltend, auf dieser Parzelle habe sich seit den 60er Jahren eine Baute befunden. Für diese liegt jedoch keine Baubewilligung in den Akten; die KBK hat auch nachträglich kein Baudossier in ihrem Archiv gefunden. Ohnehin ist von der ursprünglichen Baute fast nichts mehr erhalten: Nach den insoweit unstreitigen Feststellungen des Kantonsgerichts wurden bei Sanierungsarbeiten ausser der Betonwand Süd alle Bauteile (Betonwände, Wände und Dach) abgebrochen und neu erstellt (mit Verweis auf den Baupolizeibericht vom 13. Oktober 2014). Diese Bauarbeiten wurden nach Auskunft des Registerhalters 2014/2015 abgeschlossen (nach einem Baustopp 2013), d.h. noch während des hängigen Wiederherstellungsverfahrens. Eine Baubewilligung wurde nicht eingeholt.
11.2. Das Kantonsgericht verneinte den Besitzstandsschutz schon mangels Baubewilligung. Dem ist jedenfalls für Art. 41c Abs. 2 GSchV zuzustimmen (vgl. oben E. 8.2 und E. 9). Nach geltendem Recht kann weder die Errichtung noch der Wiederaufbau von Bauten für eine Bauunternehmung im Gewässerraum bewilligt werden (Art. 41c Abs. 1 und 2 GSchV).
11.3. Im Übrigen würden der Bewilligung des Wiederaufbaus am bisherigen Standort, in der roten Gefahrenzone für Hochwasser und Lawinen, auch wichtige Anliegen der Raumplanung entgegenstehen (vgl. oben E. 10). In erheblich hochwasser- oder lawinengefährdeten Gewässerräumen kann sogar der Abbruch rechtskräftig bewilligter Bauten und Anlagen (unter Widerruf der Baubewilligung) angeordnet werden (vgl. Parlamentarische Initiative Schutz und Nutzung der Gewässer Bericht der Kommission für Umwelt, Raumplanung und Energie des Ständerates vom 12. August 2008, BBl 2008, 8060 zu <ref-law>). Erst recht können formell rechtswidrige Bauten und Anlagen in solchen Gebieten nicht nachträglich bewilligt werden.
Es kann daher offenbleiben, ob die ursprüngliche Baute aus den 1960er Jahren trotz fehlender Baubewilligung raumplanungsrechtlich den erweiterten Besitzstandsschutz nach Art. 24c RPG beanspruchen konnte, weil sie nach dem zum Zeitpunkt ihrer Errichtung geltenden materiellen Recht bewilligungsfähig war (so die bisherige Rechtsprechung, vgl. zuletzt Urteil 1C_311/2012 vom 28. August 2013 E. 5.3, in: ZBl 115/2014 207, und 1C_345/2014 vom 17. Juni 2015, E. 3, in: URP 2015 706; RDAF, 2016 I 394 [beide betreffen denselben Fall] und die herrschende Lehre; vgl. z.B. WALDMANN, a.a.O., Rz. 6.58 Fn. 130; WILLI, a.a.O., S. 22 f.; a.A. wohl RUDOLF MUGGLI, in: Praxiskommentar RPG, Bauen ausserhalb der Bauzone, Art. 24c Rz. 15; DERSELBE, in: Aemisegger/Kuttler/Moor/Ruch, RPG-Kommentar, Art. 24c Rz. 11).
12.
Zu prüfen ist schliesslich die Nutzung des Grundstücks als Lagerplatz für Container, Baumaterial, Aushub-, Abbruch- und Abraummaterial.
12.1. Die Beschwerdeführer behaupten, diese Nutzung sei 1967, zusammen mit der Garage samt Werkräumen auf Parzelle Nr. 2546 (GBV 1443), bewilligt worden. Dafür finden sich jedoch in der Baubewilligung und im Baudossier keine Anhaltspunkte. Für die übrigen Parzellen existiert ohnehin keine Baubewilligung.
12.2. Die fragliche Nutzung kann im Gewässerraum auch nachträglich nicht bewilligt werden, weil das Materiallager weder standortgebunden ist noch im öffentlichen Interesse liegt (Art. 41c Abs. 1 GSchV).
12.3. Im Übrigen müsste die nachträgliche Baubewilligung für das Materiallager in der Gefahrenzone für Hochwasser und Lawinen auch aufgrund entgegenstehender, überwiegender öffentlicher Interessen versagt werden (Art. 24c Abs. 5 RPG und <ref-law>), selbst wenn die übrigen Voraussetzungen des Besitzstandsschutzes gemäss Art. 24 Abs. 1 RPG und Art. 41 f. RPV vorliegen sollten. Die privaten Interessen an der Aufrechterhaltung einer Grundstücksnutzung wiegen nicht schwer, wenn diese ohne nennenswerte bauliche Vorkehren erfolgt sind, d.h. keine erheblichen Investitionen auf dem Spiel stehen. Diesfalls vermögen sogar weniger gewichtige öffentliche Interessen eine Anpassung an neue Rechtsvorschriften zu rechtfertigen (vgl. WILLI, a.a.O.; S. 49; Urteil 1P.418/2002 vom 16. Dezember 2002 E. 4.5; vgl. auch ZAUGG/LUDWIG, a.a.O., Art. 3 N. 2a, wonach die Besitzstandsgarantie nach Berner Recht in solchen Fällen gar nicht angerufen werden kann).
13.
Der Vollständigkeit halber ist festzuhalten, dass auch eine gewässerschutzrechtliche Bewilligung des Baulagers fehlt, wie das BAFU in seiner Vernehmlassung hervorhebt.
13.1. In den besonders gefährdeten Bereichen bedürfen die Erstellung und die Änderung von Bauten und Anlagen sowie Grabungen, Erdbewegungen und ähnliche Arbeiten einer kantonalen Bewilligung, wenn sie die Gewässer gefährden können (<ref-law> i.V.m. Art. 32 GSchV). Zu den besonders gefährdeten Bereichen im Sinne dieser Bestimmung zählt der Gewässerschutzbereich AU zum Schutz nutzbarer unterirdischer Gewässer und ihrer Randgebiete (Art. 29 Abs. 1 lit. a und Ziff. 111 Abs. 1 Anh. 4 GSchV). Gewerbliche und industrielle Betriebe, die wassergefährdende Stoffe erzeugen, verwenden, umschlagen, befördern oder lagern, können die Gewässer gefährden und sind daher im Gewässerschutzbereich AU bewilligungspflichtig (BUWAL, Wegleitung Grundwasserschutz 2004 S. 63 und 65).
13.2. Vorliegend ergibt sich aus den Akten, dass Abbruch- und Abraummaterial auf dem Grundstück gelagert wurde. Auch wenn es sich - wie die Beschwerdeführer geltend machen - nicht um eine Deponie, sondern lediglich um ein Zwischenlager handelte, wäre dafür aufgrund des Gefährdungspotenzials eine gewässerschutzrechtliche Bewilligung erforderlich (Wegleitung Grundwasserschutz S. 82; vgl. auch Urteil 1A.224/2006 vom 25. Juni 2007 E. 4.3 und - zu den Anforderungen an ein Zwischenlager - Art. 29 Abs. 1 Abfallverordnung vom 4. Dezember 2015 [VVEA; SR 814.600]).
14.
Sind die bestehenden Bauten und Anlagen nach dem Gesagten formell rechtswidrig und können sie auch nachträglich nicht bewilligt werden, so müssen sie grundsätzlich beseitigt werden, sofern die Wiederherstellung nicht unverhältnismässig und der Wiederherstellungsanspruch nicht verwirkt ist (vgl. <ref-ruling> E. 6 S. 364 f. mit Hinweisen).
Das Kantonsgericht hielt fest, die Bauten und das Materialdepot widersprächen in grundlegender Weise dem Raumplanungsrecht; das öffentliche Interesse an der Wiederherstellung des rechtmässigen Zustands überwiege die privaten Interessen der Beschwerdeführer an der Weiternutzung des Standorts, auch wenn sie derzeit (mangels homologierten Zonenplans der Gemeinde) noch nicht über einen Ersatzstandort verfügten. Die Beschwerdeführer zeigen nicht substanziiert auf, inwiefern diese Beurteilung Bundesrecht verletzt; dies ist auch nicht ersichtlich.
15.
Nach der bundesgerichtlichen Rechtsprechung verwirkt der Anspruch der Behörden auf Wiederherstellung des rechtmässigen Zustands im Interesse der Rechtssicherheit grundsätzlich in 30 Jahren, sofern der Kanton keine kürzeren Verwirkungsfristen vorsieht.
15.1. Art. 57 Abs. 4 des Walliser Baugesetzes vom 15. Dezember 2016 (BauG; BGS 705.1) sieht vor, dass die Wiederherstellung des rechtmässigen Zustands nach Ablauf von zehn Jahren seit Erkennbarkeit der Rechtswidrigkeit nur verlangt werden kann, wenn zwingende Interessen es verlangen; die "absolute Verjährung" tritt 20 Jahre nach Beendigung der Bauarbeiten ein. Nach einhelliger Auffassung findet diese kürzere Frist jedoch keine Anwendung, wenn es um die Durchsetzung von Bundesrecht, insbesondere den Abbruch von Bauten und Anlagen ausserhalb der Bauzone, geht (vgl. Urteil 150/2016 vom 20. September 2016 E. 10.4 und 10.5 mit zahlreichen Hinweisen; bestätigt in Urteil 1C_249/2017 vom 14. November 2017 E. 4.1.1.).
15.2. Vorliegend verneinte das Kantonsgericht die Verwirkung, weil die Bauten und Anlagen erneuert, saniert, renoviert, teilweise abgebrochen und wieder aufgebaut worden seien, d.h. die Bauten aus den 60er Jahren heute nicht mehr existierten, sondern die Wiederherstellung die kontinuierlich entstandene neue Bausubstanz betreffe. Gleiches gelte für die als Depot genutzte Fläche, die im Lauf der Jahre immer mehr Fläche in Anspruch genommen hätte (vgl. <ref-ruling> E. 8.3 S. 368).
Es ist unstreitig, dass die abzubrechenden Bauten (erstellt 1993 bzw. 2013-2015) noch keine 30 Jahre bestehen. Die Beschwerdeführer bestreiten dies dagegen für das Materialdepot, zeigen aber nicht auf, inwieweit der angefochtene Entscheid in diesem Punkt offensichtlich unrichtig sei. Dies ist auch nicht ersichtlich. Ist - wie hier - der Umfang der Lagernutzung weder in einer Baubewilligung festgelegt noch durch bauliche Vorkehren (z.B. Sockel, Überdachung) begrenzt, hängt sie einzig von den Bedürfnissen des Betreibers ab. Mit der Entwicklung des Unternehmens nehmen diese zu und beanspruchen erfahrungsgemäss immer mehr Raum. Auch die Zusammensetzung des abgelagerten Materials und dessen Bearbeitung unterliegen einem ständigen Wandel. Unter diesen Umständen kann von vornherein keine Verwirkung eintreten.
15.3. Im Übrigen hielt das Kantonsgericht zutreffend fest, dass die Wiederherstellung sogar noch nach Ablauf von 30 Jahren verlangt werden könnte, weil zwingende öffentliche Interessen sie verlangten (vgl. Urteil 1C_726/2013 vom 24. November 2014 E. 4, in ZBl 117/2016 99; RDAF, 2017 I 388, mit Hinweisen). Hierfür kann auf das oben Gesagte verwiesen werden.
16.
Die Beschwerde 1C_476/2019 ist somit abzuweisen, soweit darauf einzutreten ist; die Beschwerde 1C_22/2019 ist abzuweisen. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig (<ref-law>) und haben keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde 1C_476/2019 wird abgewiesen, soweit darauf einzutreten ist; die Beschwerde 1C_22/2019 wird abgewiesen.
2.
Die Gerichtskosten von insgesamt Fr. 6'000.-- werden den Beschwerdeführern auferlegt.
3.
Es werden keine Parteientschädigungen zugesprochen.
4.
Dieses Urteil wird den Beschwerdeführern, der Einwohnergemeinde Saas-Balen, dem Staatsrat des Kantons Wallis, dem Kantonsgericht Wallis, Öffentlichrechtliche Abteilung, dem Bundesamt für Raumentwicklung und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 6. April 2020
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Gerber