Sachverhalt: A. Das Kantonsgericht Wallis sprach X._ am 20. September 2012 der mehrfachen versuchten und der mehrfachen vollendeten sexuellen Handlungen mit Kindern, der mehrfachen versuchten und der mehrfachen vollendeten sexuellen Nötigung, der mehrfachen versuchten Vergewaltigung, der Vergewaltigung, der qualifizierten Vergewaltigung, der einfachen Körperverletzung und der Drohung schuldig und verurteilte ihn zu einer Freiheitsstrafe von elf Jahren und acht Monaten. Das Gericht schob den Vollzug der Strafe zugunsten einer stationären therapeutischen Massnahme auf. Am 4. November 2016 übermittelte die Dienststelle für Straf- und Massnahmenvollzug, Amt für Sanktionen und Begleitmassnahmen, dem Straf- und Massnahmenvollzugsgericht des Kantons Wallis das Dossier betreffend X._ für die jährliche Überprüfung der Massnahme. Das Straf- und Massnahmenvollzugsgericht ordnete unter anderem die Einholung eines forensisch-psychiatrischen Gutachtens bzw. eines Ergänzungsgutachtens an. Die Massnahme lief am 19. September 2017 ab. Am 15. Dezember 2017 stellte das Amt für Sanktionen und Begleitmassnahmen dem Straf- und Massnahmenvollzugsgericht den Antrag, die stationäre therapeutische Massnahme sei aufzuheben und stattdessen die Verwahrung anzuordnen. Mit Entscheid vom 8. Mai 2018 hob das Straf- und Massnahmenvollzugsgericht die stationäre therapeutische Massnahme aufgrund festgestellter Aussichtslosigkeit auf und ordnete die Verwahrung an. Auf das Entschädigungsbegehren von X._ im Zusammenhang mit dem fehlenden Hafttitel zwischen dem 21. September 2017 und dem 18. Januar 2018 trat es nicht ein. Schliesslich ordnete es den Verbleib von X._ in Sicherheitshaft an. B. Die dagegen von X._ geführte Beschwerde wies das Kantonsgericht Wallis am 22. Oktober 2018 ab. Es bestätigte den Entscheid des Straf- und Massnahmenvollzugsgerichts hinsichtlich der Aufhebung der Massnahme und der Anordnung der Verwahrung. Weiter stellte es fest, dass die Inhaftierung von X._ vom 20. September 2017 bis zum 18. Januar 2018 mangels gültigen Hafttitels formell unrechtmässig war. Den Entschädigungsantrag wies es ebenfalls ab. Es ordnete an, dass X._ zur Sicherung der Verwahrung in Sicherheitshaft verbleibt. C. C.a. X._ führt Beschwerde in Strafsachen. Er beantragt, der vorinstanzliche Entscheid sei aufzuheben. Auf die Anträge auf Verlängerung der stationären therapeutischen Massnahme, Aufhebung der stationären therapeutischen Massnahme und Verwahrung sei nicht einzutreten. Eventualiter sei die Sache an die erste Instanz, subeventualiter an die Vorinstanz zur Durchführung eines ordnungsgemässen Verfahrens zurückzuweisen. Subsubeventualiter sei der Antrag auf Verwahrung abzuweisen und die stationäre therapeutische Massnahme um zwei Jahre zu verlängern. Er sei für die rechtswidrige Haft vom 20. September 2017 bis zum 18. Januar 2018 pro Hafttag mit einer Genugtuung von Fr. 300.-- zu entschädigen. Für das bundesgerichtliche Verfahren beantragt X._ die unentgeltliche Rechtspflege und Verbeiständung. C.b. Das Kantonsgericht beantragt unter Verweis auf die Erwägungen des angefochtenen Entscheids die Abweisung der Beschwerde. Das Amt für Sanktionen und Begleitmassnahmen beantragt ebenfalls die Abweisung der Beschwerde. X._ wurde das Replikrecht gewährt. Er liess durch seinen Anwalt auf eine Stellungnahme verzichten. Am 30. Januar 2019 reichte X._ persönlich nach Ablauf der mit Verfügung vom 5. Dezember 2018 angesetzten Frist zur Stellungnahme eine Eingabe mit Beilagen ein.