Sachverhalt: A. A.C._ und B.C._ haben im Weiler V._ auf dem Territorium U._ ein Grundstück. Dieses wurde infolge von Unwettern im Lötschental am 10./11. Oktober 2011 überschwemmt und mit Kies, Geröll und Schwemmholz überdeckt. Nach Durchführung der dringendsten Aufräumarbeiten, die von den Gemeinden W._ und U._ organisiert wurden, und der Erstellung eines provisorischen Schutzdamms, hat die Armee im Frühling 2012 in V._ Material aufgeladen und abgeführt. Davon war auch das Grundstück von A.C._ und B.C._ betroffen. In der Folge gelangten diese mit Schreiben vom 19. Juni 2012 an die Gemeinden U._ und W._. Sie beanstandeten, dass diese bzw. die Armee im März 2012 - ohne sie als Eigentümer zu informieren - Kies und weiteres Material abgeführt haben, weshalb u.a. das Trassee vor ihrer Hütte nun ca. 80 cm tiefer als die Strasse liege. Gefällte Bäume und Schwemmholz lägen zudem "zu Bergen aufgetürmt" auf ihrem Grundstück. Gestützt auf einen Augenschein, an welchem neben A.C._ und B.C._ ein Vertreter der kantonalen Dienststelle für Flussbau und die Gemeindevertreter der Gemeinde U._ und der Gemeinde W._ teilnahmen, hielt die Gemeinde U._ mit Schreiben vom 6. Juli 2012 fest, dass die beiden Gemeinden darauf hinwirken würden, damit im Rahmen einer militärischen Dienstleistung Terrainarbeiten im Raume der Hütte von A.C._ und B.C._ erfolgen können, dass bei einem allfälligen Einsatz des Militärs oder anderer Organisationen (Feuerwehr und Zivilschutz) diese vorgängig orientiert würden. Über allenfalls entstehende Unkosten auch bei Leistungen des Militärs und des Zivilschutzes sei keine verbindliche Regelung getroffen worden. Diese Terrainarbeiten wurden offenbar nicht an die Hand genommen. B. Mit Schreiben vom 24. Juni 2014 intervenierten A.C._ und B.C._ erneut. Es sei unzulässig, dass eine Gemeinde oder der Kanton auf einem privaten Grundstück Material entferne. Der dadurch entstandene Schaden sei zu ersetzen. Gleichzeitig unterbreiteten sie der Gemeinde einen Vorschlag zur Behebung des Schadens. Nachdem die Gemeinde U._ A.C._ und B.C._ mitgeteilt hatte, dass ihr Anliegen an einer gemeinsamen Gemeinderatssitzung der Gemeinden U._ und W._ behandelt werde, präzisierten diese, dass es sich nicht um die Unwetterschäden vom Oktober 2011 handle, sondern um das widerrechtliche Entfernen von Kiesmaterial auf ihrem Grundstück in V._. Am 6. Mai 2015 reichten A.C._ und B.C._ eine Offerte für die Geländeanpassungen von Fr. 66'321.30 der Gemeinde U._ ein. Am 10. Juli 2015 erhoben sie Klage auf Zahlung von Fr. 66'321.30 und Fr. 14'688.--. Das Bezirksgericht Leuk/Westlich Raron beschränkte das Verfahren auf die Frage der Verjährung und wies mit Urteil vom 1. Juni 2016 die Klage ab. Auch die Berufung beim Kantonsgericht des Kantons Wallis war erfolglos (2. November 2018), da der Schaden spätestens am 19. Juni 2012 bekannt gewesen, die Verjährung nicht unterbrochen worden sei, das Schreiben vom 6. Juli 2012 keine Schuldanerkennung darstelle, weshalb die Forderung im Juli 2013 definitiv verjährt sei, und die Berufung auf die Verjährung auch nicht rechtsmissbräuchlich erfolgt sei. C. Vor Bundesgericht beantragen A.C._ und B.C._ mit Beschwerde in Zivilsachen, das Urteil des Kantonsgerichts vom 2. November 2018 aufzuheben und dementsprechend die Kosten der vorinstanzlichen Verfahren neu zu verlegen. Während das Kantonsgericht des Kantons Wallis auf eine Vernehmlassung und einen Antrag verzichtet, beantragt die Gemeinde U._ vernehmlassungsweise die Abweisung der Beschwerde.