Sachverhalt:
A.
A._ wird zusammengefasst vorgeworfen, als Barmann im Hotel C._ in U._ die 14-jährige B._ betrunken gemacht zu haben. Er habe mit ihr im Fumoir der Bar geflirtet, sie anschliessend geküsst und ihr gegen den Willen die Zunge in den Mund gesteckt. Die stark betrunkene B._ habe zwar begriffen, was um sie herum geschehe, sei aber unsicher auf den Beinen gestanden und habe sich nicht mehr wirksam gegen A._ wehren können. Dieser habe sie in der Folge in einen Aufenthaltsraum im zweiten Untergeschoss des Hotels gebracht und dort mit Gewalt und gegen ihren Willen verschiedene sexuelle Handlungen vorgenommen. Namentlich soll A._ die minderjährige B._ zu Oral- und ungeschütztem Analverkehr gezwungen haben. Zudem sei er in ihre Vagina eingedrungen, habe den Penis aber wieder herausgezogen, weil B._ (nachfolgend "Privatklägerin") ihre Menstruation gehabt und sich ein Tampon in der Vagina befunden hätte.
B.
Das Kreisgericht Oberwallis erkannte A._ am 2. Oktober 2019 der sexuellen Handlungen mit Kindern, der sexuellen Nötigung und der versuchten Vergewaltigung schuldig und bestrafte ihn mit einer unbedingten Freiheitsstrafe von 48 Monaten. Es verwies ihn für fünf Jahre aus der Schweiz.
Die gegen dieses Urteil von A._ erhobene Berufung wies das Kantonsgericht Wallis am 22. April 2020 ab.
C.
A._ führt Beschwerde an das Bundesgericht. Er beantragt einen Freispruch vom Vorwurf der sexuellen Nötigung und der versuchten Vergewaltigung. Er sei mit einer Freiheitsstrafe von maximal 24 Monaten zu bestrafen. Zudem seien die Kosten neu zu verlegen und die zu bezahlende Parteientschädigung zu reduzieren. Eventualiter sei die Sache zur Neubeurteilung an das Kantonsgericht zurückzuweisen. A._ ersucht ferner um unentgeltliche Rechtspflege und Verbeiständung. Sein bisheriger Rechtsvertreter, Rechtsanwalt Fabian Williner, teilte dem Bundesgericht am 12. August 2020 mit, dass das Mandat beendet worden sei.

Erwägungen:
1.
1.1. Der Beschwerdeführer macht geltend, die vorinstanzliche Sachverhaltsfeststellung zur tatsituativen Zwangssituation, welche die Vorwürfe der versuchten Vergewaltigung und sexuellen Nötigung (und damit auch betreffend die Strafzumessung) betreffe, sei offensichtlich unrichtig. Die Vorinstanz mutmasse ohne Verweis auf die Akten, dass er sich die familiären Probleme der Privatklägerin angehört und deren Vertrauen gewonnen habe. Dies sei falsch. Er habe die Familie der Privatklägerin gemäss vorinstanzlichem Urteil nur ein einziges Mal bedient und sich dabei nicht besonders gut angestellt. Durch das kurzzeitige Gespräch habe kaum ein Vertrauensverhältnis zwischen der Privatklägerin und dem Beschwerdeführer als Hotelangestellten bestanden. Seine Aussage gegenüber der Polizei, dass die Privatklägerin seine sexuellen Handlungen nicht gewollt habe, erstaune zudem kaum. Dies sei eine reine im Nachgang an die Inhaftierung getätigte Aussage. Wäre er nicht inhaftiert worden, hätte er diese Vermutung auch nicht aufgestellt. Anders könne die Aussage nicht interpretiert werden, wobei auch zu berücksichtigen sei, dass damals kein Dolmetscher anwesend gewesen sei, der die Befragung übersetzt hätte. Schliesslich lasse sich aus der Angetrunkenheit der Privatklägerin nichts in Bezug auf deren Willen ableiten. Diese sei passiv geblieben und habe dem Beschwerdeführer weder im Fumoir noch im Untergeschoss signalisiert, dass sie mit seinen Handlungen nicht einverstanden gewesen sei. Er habe keine Gewalt oder sonstigen Nötigungsmittel anwenden müssen, damit es zu sexuellen Handlungen gekommen sei. Zusammengefasst habe die Vorinstanz "das Recht in Bezug auf die Thematik der Nötigungsmittel" falsch angewandt.
1.2. Die Vorinstanz verweist zu den Sachverhaltselementen, aus denen sie die Nötigungshandlung ableitet, auf das erstinstanzliche Urteil (Urteil S. 34) und fasst diese (im rechtlichen Teil) zusammen (Urteil S. 36 f.). Sie hält zunächst fest, dass ein erheblicher Alters- und Grössenunterschied zwischen dem Beschwerdeführer und der Privatklägerin bestanden habe. Letzere sei bloss 14 Jahre alt und ausserdem betrunken gewesen, was der Beschwerdeführer realisiert habe. Er habe durch sein Nachschenken von Wodka dazu beigetragen und sich die familiären Probleme der Privatklägerin angehört, Verständnis gezeigt und sie getröstet. Er habe dadurch die Gemütsverfassung der Privatklägerin erkannt und mit der Diskussion eine Nähe zu ihr ermöglicht. Auch wenn keine nähere Beziehung zu ihr bestanden habe, so habe sie sich schon mehrere Tage im Hotel aufgehalten und sei davon ausgegangen, sie könne einem Hotelangestellten, der über einen Generalschlüssel verfüge, vertrauen. Der Beschwerdeführer habe die Privatklägerin bewusst über die Treppen ins zweite, menschenleere Untergeschoss geführt. Beim Beginn der sexuellen Handlungen hätten sie sich in einer engen Nische befunden, wo die Privatklägerin nur über die verhältnismässig steile Treppe hätte fliehen können. Die betrunkene Privatklägerin sei von den Handlungen des Beschwerdeführers überrascht worden. Sie habe sich verbal nicht zur Wehr gesetzt und sich mehrheitlich passiv verhalten, während der Beschwerdeführer den Verlauf der sexuellen Handlungen bestimmt habe. Dieser habe die deutlich jüngere Privatklägerin zunächst zum Oralsex geleitet, sie "ausgegriffen", sich und die Privatklägerin soweit nötig ausgezogen, die Jugendliche auf das Sofa "befördert", wo sie sich in der Bauchlage gegen die weiteren Handlungen, namentlich gegen die Penetration, schlecht habe wehren können. Der Beschwerdeführer hätte sich angesichts des Alters und des betrunkenen Zustands der Jugendlichen hinterfragen müssen, ob sie mit den von ihm alleine initiierten sexuellen Handlungen einverstanden sei, zumal die Privatklägerin beim Oralsex mehr oder weniger erfolgreich versucht habe, sich zu befreien und den Beschwerdeführer wegzustossen. Dadurch habe sie ihren Unwillen erkennbar manifestiert. Der Beschwerdeführer habe zudem in der Befragung vom 24. Dezember 2018 angegeben, er glaube, die Privatklägerin habe die sexuellen Handlungen nicht gewollt (Urteil S. 36 f.).
1.3.
1.3.1. Eine Vergewaltigung nach Art. 190 Abs. 1 StGB begeht, wer eine Person weiblichen Geschlechts zur Duldung des Beischlafs nötigt, namentlich indem er sie bedroht, Gewalt anwendet, sie unter psychischen Druck setzt oder zum Widerstand unfähig macht. Eine sexuelle Nötigung im Sinne von Art. 189 Abs. 1 StGB ist gegeben, wenn der Täter eine Person zur Duldung einer beischlafsähnlichen oder einer ähnlichen Handlung nötigt, namentlich indem er sie bedroht, Gewalt anwendet, sie unter psychischen Druck setzt oder zum Widerstand unfähig macht. Die in beiden Tatbeständen beispielhaft genannten Nötigungsmittel stimmen vollständig überein.
1.3.2. Die sexuellen Nötigungstatbestände verbieten den Angriff auf die sexuelle Freiheit. Sie gelten als Gewaltdelikte und sind damit prinzipiell als Akte physischer Aggression zu verstehen. Dabei stellt aber die Tatbestandsvariante des "Unter-psychischen-Druck-Setzens" klar, dass sich die tatbestandsmässige Ausweglosigkeit der Situation auch ergeben kann, ohne dass der Täter eigentliche Gewalt anwendet. Es kann vielmehr genügen, dass dem Opfer ein Widersetzen unter solchen Umständen aus anderen Gründen nicht zuzumuten ist. Diese Umstände müssen eine Qualität erreichen, die sie in ihrer Gesamtheit als instrumentalisierte, sogenannte strukturelle Gewalt erscheinen lassen. Ob die tatsächlichen Verhältnisse die tatbeständlichen Anforderungen eines Nötigungsmittels erfüllen, lässt sich erst nach einer umfassenden Würdigung der konkreten Umstände entscheiden (<ref-ruling> E. 2.2 mit Hinweis). Die Nötigungstatbestände sind grundsätzlich auf Erwachsene zugeschnitten. Erwachsenen mit entsprechenden individuellen Fähigkeiten ist eine stärkere Gegenwehr zuzumuten als Kindern (<ref-ruling> E. 3a/bb; <ref-ruling> E. 2b). Je nach den Umständen und den Beziehungen zum Täter kann ein Kind wegen seiner kognitiven Unterlegenheit und seiner Abhängigkeit in emotionaler und sozialer Hinsicht den Bedürfnissen des Täters mehr oder weniger ausgeliefert sein (Urteil 6B_1265/2019 vom 9. April 2020 E. 3.3.1 ff., zur Publikation vorgesehen).
1.4. Der Beschwerdeführer greift unter dem Titel "Rechtsverletzungen" einerseits einzelne tatsächliche Feststellungen im angefochtenen Entscheid auf, die er als "aktenwidrig und falsch" bezeichnet und bemängelt andererseits, dass die Vorinstanz das "Recht falsch angewandt" habe. Er vermengt dabei Tat- und Rechtsfragen ohne die Verletzung einer konkreten Rechtsnorm zu rügen. Soweit er seine Kritik an der als rechtsfehlerhaft erachteten Sachverhaltsfeststellung der Vorinstanz ansetzt, ist zu berücksichtigen, dass das Bundesgericht seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde legt (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts kann vor Bundesgericht nur gerügt werden, wenn sie willkürlich im Sinne von Art. 9 BV ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG). Das Bundesgericht hat sich in seiner bisherigen Rechtsprechung ausführlich dazu geäussert, wann Willkür vorliegt und welche Begründungsanforderungen an eine solche Rüge zu stellen sind. Darauf kann verwiesen werden. Dem Grundsatz "in dubio pro reo" kommt in seiner Funktion als Beweiswürdigungsregel im Verfahren vor dem Bundesgericht keine über das Willkürverbot von Art. 9 BV hinausgehende Bedeutung zu (<ref-ruling> E. 1.3.1, 114 E. 2.1; Urteil 6B_1031/2019 vom 1. September 2020 E. 1.2.1; je mit Hinweisen).
1.5. Was der Beschwerdeführer gegen die im Zusammenhang mit der tatsituativen Zwangssituation stehenden, tatsächlichen Feststellungen der Vorinstanz vorbringt, erschöpft sich weitgehend in einer appellatorischen Kritik am angefochtenen Urteil, auf welche das Bundesgericht praxisgemäss nicht eintritt. Das vom Beschwerdeführer erwähnte Gespräch mit der Privatklägerin an der Bar ist von untergeordneter Bedeutung, zumal es bloss die Anbahnung des Kontakts zur Privatklägerin betrifft. Im Übrigen geht auch die Vorinstanz davon aus, dass keine nähere Beziehung zwischen dem Beschwerdeführer und der Privatklägerin bestand (Urteil S. 36). Ausserdem bestätigte der Beschwerdeführer selbst das Gespräch und dessen Thematik. Er gab an, die Privatklägerin getröstet zu haben (Urteil S. 30). Die Vorinstanz hält alsdann gestützt auf die ihrer Ansicht nach glaubhaften Aussagen der Privatklägerin für erwiesen, dass sich diese zu Beginn der Handlungen im Untergeschoss gewehrt habe, indem sie mehr oder weniger erfolgreich versucht hätte, sich mittels Stossen aus ihrer misslichen Lage zu befreien (Urteil S. 18). Inwiefern diese Sachverhaltsfeststellung willkürlich sein soll, zeigt der Beschwerdeführer nicht auf. Er beschränkt sich darauf zu behaupten, die Privatklägerin habe sich passiv verhalten. Seine selbstbelastende Aussage, die Privatklägerin habe die sexuellen Handlungen nicht gewollt, wertet die Vorinstanz als Indiz, stützt sich aber auf verschiedene weitere Umstände, mit denen sich der Beschwerdeführer in seiner Beschwerde nicht auseinandersetzt. Dass die von der Vorinstanz als Sachgericht gezogenen Schlüsse nicht mit seiner Darstellung übereinstimmen oder eine andere Würdigung ebenfalls vertretbar oder gar zutreffender erscheint, genügt für die Annahme von Willkür nicht (<ref-ruling> E. 4.2 mit Hinweisen).
1.6. Die Vorinstanz schliesst - soweit der Beschwerdeführer nicht ohnehin Gewalt anwandte - zu Recht auf eine ausweglose Situation, in der sich die Privatklägerin wehrte, soweit sie konnte, bzw. sich grösstenteils nicht mehr wehren konnte. Sie berücksichtigt dabei die List des Beschwerdeführers, der die alkoholisierte Privatklägerin ins zweite Untergeschoss statt auf ihr Zimmer brachte sowie die dort eingeschränkt vorhandenen Fluchtmöglichkeiten. Auch das grosse Alters- und damit einhergehende Machtgefälle zwischen der jugendlichen Privatklägerin und dem Beschwerdeführer sowie dessen sich aus seiner beruflichen Tätigkeit als Hotelangestellter ergebende Vertrauensposition bezieht die Vorinstanz - nebst der konkreten Tatsituation, die für sich alleine genommen bereits für eine Zwangslage ausreicht - in ihre Gesamtwürdigung ein. Aufgrund des willkürfrei festgestellten Sachverhalts durfte die Vorinstanz von einer tatsituativen Zwangssituation im Sinne von Art. 189 und Art. 190 StGB ausgehen.
2.
2.1. Der Beschwerdeführer kritisiert den für die Strafzumessung von der Vorinstanz festgestellten Sachverhalt als willkürlich. Die Strafe fällt seiner Auffassung nach zu hoch aus, selbst wenn die Vorwürfe der sexuellen Nötigung und der versuchten Vergewaltigung bestehen blieben. Konkret macht der Beschwerdeführer geltend, die Vorinstanz sei zu Unrecht von einem Vertrauensverhältnis ausgegangen. Dabei sei unzutreffend, dass er der Privatklägerin suggeriert habe, er bringe sie auf sein Zimmer. Schliesslich habe er nicht gewusst, dass die Privatklägerin jünger als 16 Jahre alt sei, auch wenn er die Verurteilung wegen sexueller Handlungen mit einem Kind akzeptiert habe.
2.2. Der Beschwerdeführer beschränkt sich mit seiner Argumentation auf appellatorische Kritik am angefochtenen Urteil. Die Vorinstanz geht bei der Strafzumessung insoweit von einem Vertrauensverhältnis aus, als die betrunkene Privatklägerin als Hotelgast darauf vertraut habe, dass der Beschwerdeführer als Hotelangestellter sie auf ihren Wunsch hin zu ihrem Zimmer bringe, zumal sie den Zimmerschlüssel nicht gefunden und aufgrund ihrer Alkoholisierung gewankt habe (Urteil S. 38). Damit setzt sich der Beschwerdeführer nicht auseinander. Seine Ausführungen zu Art. 187 Ziff. 4 StGB beziehen sich sodann auf einen vor Vorinstanz nicht angefochtenen Punkt. Inwiefern die Vorinstanz in diesem Zusammenhang die Strafe falsch bemessen haben soll, begründet der Beschwerdeführer nicht. Soweit er sich schliesslich ohne konkreten Bezug auf den angefochtenen Entscheid auf Vergleichsfälle der bundesgerichtlichen Praxis beruft und damit die mangelnde Plausibilität der vorinstanzlichen Strafe belegen will, ist ihm nicht zu folgen. Die Strafzumessung beruht auf einer individualisierten Beurteilung aller massgeblichen Umstände und kann nicht durch den blossen Verweis auf die in anderen Fällen ausgesprochenen Strafen in Frage gestellt werden (Urteile 6B_312/2016 vom 23. Juni 2016 E. 1.6.2; 6B_213/2010 vom 2. Juli 2010 E. 4.4; je mit Hinweisen).
3.
Die Anträge betreffend die Verfahrenskosten und die Parteientschädigung begründet der Beschwerdeführer soweit verständlich mit der Gutheissung seiner Rügen im Beschwerdeverfahren. Da sie sich als unbegründet erweisen, ist auf den Kosten- und Entschädigungspunkt nicht weiter einzugehen.
4.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Das Gesuch um unentgeltliche Rechtspflege ist ebenfalls abzuweisen, da die Beschwerde von vornherein aussichtslos war (Art. 64 Abs. 1 BGG). Der angespannten finanziellen Situation des Beschwerdeführers ist bei der Bemessung der Gerichtskosten Rechnung zu tragen. Die Kosten sind dem unterliegenden Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3.
Der Gerichtskosten von Fr. 1'200.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Parteien und dem Kantonsgericht des Kantons Wallis, I. Strafrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 20. November 2020
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Reut