Sachverhalt:
A.
Das Strafgericht Basel-Stadt sprach A._ am 12. November 1998 der mehrfachen versuchten, teilweise qualifizierten Vergewaltigung, der mehrfachen versuchten und vollendeten, teilweise qualifizierten sexuellen Nötigung sowie der mehrfachen versuchten Nötigung schuldig. Es verurteilte ihn zu einer Zuchthausstrafe von 5 1⁄2 Jahren, schob deren Vollzug wie auch den Vollzug einer für vollziehbar erklärten Freiheitsstrafe von 5 Tagen auf und wies A._ in eine Heil- und Pflegeanstalt ein.
B.
B.a. Vom 12. November 1998 bis zum 7. Dezember 1998 befand sich A._ in den Universitären Psychiatrischen Kliniken Basel (UPK). Am 7. Dezember 1998 erfolgte seine Versetzung in das Massnahmenzentrum St. Johannsen (heute Justizvollzugsanstalt St. Johannsen; nachfolgend: JVA St. Johannsen), von wo er am 11. Juli 1999 nach Spanien flüchtete. In Spanien delinquierte A._ erneut. Er wurde am 5. September 1999 verhaftet und am 17. Juli 2000 wegen qualifizierten sexuellen Angriffs zu einer Freiheitsstrafe von 12 Jahren verurteilt. Der Vollzug dieser Freiheitsstrafe endete am 1. September 2011.
B.b. Am 5. September 2011 wurde A._ an die Schweiz ausgeliefert. Mit Beschluss vom 20. Dezember 2011 verlängerte das Strafgericht Basel-Stadt die von ihm am 12. November 1998 nach altem Recht angeordnete Einweisung in eine Heil- und Pflegeanstalt unter dem Titel der stationären Massnahme gemäss <ref-law> um fünf Jahre. Seither wurde die Massnahme wiederholt verlängert, letztmals rechtskräftig bis zum 31. Januar 2021.
C.
Am 15. Juli 2020 hiess das Appellationsgericht des Kantons Basel-Stadt den Rekurs von A._ gegen die abschlägigen Entscheide des Amts für Justizvollzug des Kantons Basel-Stadt, Abteilung Straf- und Massnahmenvollzug (nachfolgend: SMV) vom 24. Mai 2019 sowie des Justiz- und Sicherheitsdepartements vom 16. Januar 2020 betreffend das Gesuch um Versetzung in eine offene Massnahmenvollzugsanstalt gut. In der Folge wurde A._, welcher sich nach Aufenthalten in den Strafanstalten Bostadel und Thorberg seit dem 11. November 2015 in der Justizvollzugsanstalt Solothurn (nachfolgend: JVA Solothurn) befand, am 24. November 2020 in die JVA St. Johannsen (geschlossene Abteilung) verlegt. Am 24. März 2021 ist A._ in die offene Abteilung der JVA St. Johannsen übergetreten.
D.
Auf Antrag des SMV um Verlängerung der stationären therapeutischen Massnahme um weitere drei Jahre, verlängerte das Strafgericht Basel-Stadt mit Beschluss vom 22. Januar 2021 die stationäre therapeutische Massnahme von A._ um zwei Jahre. Die von A._ dagegen erhobene Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt am 30. Juni 2021 ab.
E.
A._ beantragt mit Beschwerde in Strafsachen, der Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 30. Juni 2021 sei aufzuheben und er sei aus dem Massnahmenvollzug zu entlassen. Eventualiter sei die Massnahme für kurze Zeit zu verlängern und das SMV anzuweisen, die bedingte Entlassung innerhalb dieser Zeitspanne in die Wege zu leiten und die entsprechenden Weisungen zu erteilen. Weiter sei er für die Überhaft seit dem 31. Januar 2021 zu entschädigen. A._ ersucht für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege und Verbeiständung.

Erwägungen:
1.
Anfechtungsgegenstand ist vorliegend ein letztinstanzlich kantonaler Entscheid, worin im Rahmen eines selbstständigen nachträglichen Verfahrens gemäss <ref-law> über die Verlängerung einer stationären therapeutischen Massnahme gemäss <ref-law> befunden wird. Es handelt sich um eine Strafsache, gegen welche die Beschwerde in Strafsachen zulässig ist (<ref-law>).
2.
2.1. Der Beschwerdeführer rügt, die Voraussetzungen für eine erneute Verlängerung der stationären therapeutischen Massnahme seien vorliegend nicht erfüllt. Zum einen habe sich das Ausmass der psychischen Störung deutlich reduziert und sei fraglich, inwiefern die diagnostizierte Störung heute noch verhaltenswirksam sei. Zum anderen fehle es an der erforderlichen Wirksamkeit der Massnahme und erweise sich deren Weiterführung als unverhältnismässig.
2.2.
2.2.1. Ist der Täter psychisch schwer gestört, so kann das Gericht gemäss <ref-law> eine stationäre Behandlung anordnen, wenn das Verbrechen oder Vergehen des Täters in Zusammenhang mit seiner psychischen Störung steht (lit. a) und zu erwarten ist, dadurch lasse sich der Gefahr weiterer mit seiner Störung in Zusammenhang stehender Taten begegnen (lit. b). Eine Massnahme, für welche die Voraussetzungen nicht mehr erfüllt sind, ist aufzuheben (<ref-law>).
2.2.2. Der mit der stationären Behandlung verbundene Freiheitsentzug beträgt in der Regel höchstens fünf Jahre (<ref-law>). Sind die Voraussetzungen für die bedingte Entlassung nach fünf Jahren noch nicht gegeben und ist zu erwarten, durch die Fortführung der Massnahme lasse sich der Gefahr weiterer mit der psychischen Störung des Täters in Zusammenhang stehender Verbrechen und Vergehen begegnen, so kann das Gericht auf Antrag der Vollzugsbehörde die Verlängerung der Massnahme um jeweils höchstens fünf Jahre anordnen (<ref-law>). Der Täter wird gemäss <ref-law> aus dem stationären Vollzug der Massnahme bedingt entlassen, sobald sein Zustand es rechtfertigt, dass ihm Gelegenheit gegeben wird, sich in der Freiheit zu bewähren. Voraussetzung für die bedingte Entlassung ist eine günstige Prognose. Die Prognose ist günstig, wenn zu erwarten ist, dass der Betroffene keine weiteren Straftaten begehen wird, die mit der behandelten Störung in Zusammenhang stehen (<ref-ruling> E. 1.2). Andererseits erfordert die Verlängerung, dass der fortbestehenden Gefahr durch die Massnahme begegnet werden kann, mithin dass der Täter überhaupt behandlungsfähig ist (<ref-ruling> E. 3.4.1; <ref-ruling> E. 3). Gemeint ist damit eine therapeutische dynamische Einflussnahme, die zu einer Verbesserung der Legalprognose führt (<ref-ruling> E. 3.6). Eine Verlängerung kann deshalb nur in Betracht gezogen werden, wenn sich davon eine therapeutische Wirkung in diesem Sinne erwarten lässt (Botschaft vom 21. September 1998 zur Änderung des Schweizerischen Strafgesetzbuches und des Militärstrafgesetzes sowie zu einem Bundesgesetz über das Jugendstrafrecht, BBl 1999 2078 f. Ziff. 213.421; <ref-ruling> E. 2.3.2; siehe auch <ref-ruling> E. 5.2.1).
2.2.3. Die stationäre therapeutische Massnahme muss verhältnismässig sein (Art. 36 Abs. 2 und 3 BV; <ref-law>). Das Verhältnismässigkeitsprinzip verlangt, dass die Massnahme geeignet ist, beim Betroffenen die Legalprognose zu verbessern. Weiter muss die Massnahme notwendig sein. Sie hat zu unterbleiben, wenn eine gleich geeignete, aber mildere Massnahme für den angestrebten Erfolg ausreichen würde. Dieses Kriterium trägt dem Aspekt des Verhältnisses zwischen Strafe und Massnahme bzw. der Subsidiarität von Massnahmen Rechnung. Schliesslich muss zwischen dem Eingriff und dem angestrebten Zweck eine vernünftige Relation bestehen (Verhältnismässigkeit i.e.S.). Das bedeutet, dass die betroffenen Interessen gegeneinander abgewogen werden müssen. Bei einer Prüfung des Zweck-Mittel-Verhältnisses fallen im Rahmen der Gesamtwürdigung auf der einen Seite insbesondere die Schwere des Eingriffs in die Freiheitsrechte des Betroffenen in Betracht. Auf der anderen Seite sind das Behandlungsbedürfnis sowie die Schwere und die Wahrscheinlichkeit künftiger Straftaten relevant (<ref-ruling> E. 5.4; <ref-ruling> E. 1.2; Urteil 6B_835/2017 vom 22. März 2018 E. 5.2.2 mit Hinweisen, nicht publ. in: <ref-ruling>). Die Dauer der (stationären) Massnahme hängt von deren Auswirkungen auf die Gefahr weiterer Straftaten ab, wobei die Freiheit dem Betroffenen nur so lange entzogen werden darf, als die von ihm ausgehende Gefahr dies zu rechtfertigen vermag. Die Massnahme dauert aber grundsätzlich so lange an, bis ihr Zweck erreicht ist oder sich eine Zweckerreichung als aussichtslos erweist (<ref-ruling> E. 2.3.3; <ref-ruling> E. 5.4; <ref-ruling> E. 3.5, 49 E. 2.1 f.; je mit Hinweisen).
2.2.4. Das Gericht stützt sich bei seinem Entscheid über die Anordnung einer Massnahme auf eine sachverständige Begutachtung (<ref-law>). Diese äussert sich über die Notwendigkeit und die Erfolgsaussichten einer Behandlung des Täters, die Art und die Wahrscheinlichkeit weiterer möglicher Straftaten und die Möglichkeiten des Vollzugs der Massnahme (<ref-law>; <ref-law>; <ref-ruling> E. 3.1; <ref-ruling> E. 4.3.1).
Das Gericht würdigt Gutachten grundsätzlich frei (<ref-law>). In Fachfragen darf es davon indessen nicht ohne triftige Gründe abweichen und Abweichungen müssen begründet werden. Auf der anderen Seite kann das Abstellen auf eine nicht schlüssige Expertise bzw. der Verzicht auf die gebotenen zusätzlichen Beweiserhebungen gegen das Verbot willkürlicher Beweiswürdigung (<ref-law>) verstossen (zum Ganzen: <ref-ruling> E. 2.1.3; <ref-ruling> E. 6.1; Urteil 6B_1172/2020 vom 21. Dezember 2020 E. 1.3.3).
2.2.5. Die vorinstanzliche Sachverhaltsfeststellung kann vor Bundesgericht nur gerügt werden, wenn sie willkürlich im Sinne von <ref-law> 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 (Art. 97 Abs. 1 und Art. 105 Abs. 1 und 2 BGG; <ref-ruling>14 E. 2.1, 88 E. 1.3.1). Die Willkürrüge muss in der Beschwerde anhand des angefochtenen Entscheids explizit vorgebracht und substanziiert begründet werden (<ref-law>). Auf ungenügend begründete Rügen oder allgemeine appellatorische Kritik am angefochtenen Entscheid tritt das Bundesgericht nicht ein (<ref-ruling>14 E. 2.1, 88 E. 1.3.1).
2.3.
2.3.1. Der Beschwerdeführer bemängelt die vorinstanzliche Auffassung, wonach von einem Fortbestehen der schweren psychischen Störung auszugehen sei. Er macht dabei geltend, dass die Führungsberichte seit Jahren positiv ausfallen würden und ihm verschiedene psychiatrische Gutachten gewisse Fortschritte attestiert hätten. Die seit langem protokollierten Therapiefortschritte hätten unter gelockerten Vollzugsbedingungen überprüft werden sollen. Bis anhin habe er jedoch keine Vollzugslockerungen erhalten. Inwiefern die diagnostizierte Störung heute noch verhaltenswirksam sei, könne deshalb nicht abschliessend beurteilt werden. Das Ausmass der psychischen Störung habe sich gemäss den Gutachten sowie den Führungs- und Therapieberichten jedoch zumindest deutlich reduziert. Die Vorinstanz habe sich mit dem vom Gesetz geforderten Schweregrad der psychischen Störung respektive mit der Tatsache, dass seit Jahren von einer massgeblichen Abschwächung berichtet werde, nicht auseinandergesetzt (vgl. Beschwerde S. 11 ff.).
2.3.2. Zur Wirksamkeit der stationären Massnahme führt der Beschwerdeführer aus, dass sowohl sämtliche Therapeuten und Therapeutinnen als auch die Gutachter übereinstimmend zum Schluss gekommen seien, dass das mit ihm Erreichbare erreicht worden sei und keine weiteren relevanten, rückfallrisikosenkenden Therapieeffekte zu erwarten seien. Damit fehle es klar an der erforderlichen Wirksamkeit der Massnahme. Eine Weiterführung der Massnahme einzig zur Sicherung, aus Angst vor einem Rückfall, sei rechtlich unzulässig (vgl. Beschwerde S. 15 f.).
2.3.3. Schliesslich wäre die Weiterführung der Massnahme auch unverhältnismässig. Er befinde sich seit über 20 Jahren in Haft respektive seit rund 12 Jahren im Massnahmenvollzug. Damit habe er seine schuldangemessene Strafe (Freiheitsstrafe von 5 1⁄2 Jahren) bereits um mehr als das Doppelte verbüsst. Seinem therapeutischen Bedürfnis sei in der Vergangenheit teils nicht hinreichend Rechnung getragen worden. Man habe von Vollzugsöffnungen abgesehen, obschon die Gutachter, die Vollzugsanstalten und sämtliche Therapeuten und Therapeutinnen die Dringlichkeit solcher Öffnungen seit Jahren mit Nachdruck empfohlen hätten. Er habe bis heute keine Gelegenheit erhalten, seine Fortschritte unter gelockerten Bedingungen unter Beweis zu stellen. Auch die früheren Entscheide des Appellationsgerichts des Kantons Basel-Stadt vom 23. Juni 2017 und 19. September 2019, in welchen die Notwendigkeit von Vollzugslockerungen betont worden seien und die im letztgenannten Entscheid enthaltene dringliche Aufforderung an die Vollzugsbehörde, einen therapeutischen Rahmen zu gestalten, der ein grösseres Mass an Flexibilität zulasse, seien einfach ignoriert worden. Die Vollzugsbehörde sei ihrer Obliegenheit zur rechtskonformen Ausgestaltung des Massnahmenvollzugs nicht nachgekommen. Die Massnahme müsste vorliegend einzig aufgrund der Untätigkeit der Vollzugsbehörde verlängert werden. Eine Verlängerung der Massnahme rechtfertige sich daher nicht (vgl. Beschwerde S. 17 ff.).
2.4.
2.4.1. Die Vorinstanz geht gestützt auf das psychiatrische Gutachten von PD Dr. med. B._ vom 3. September 2018 und auf dessen Ergänzungsgutachten vom 31. Dezember 2020 davon aus, dass die zum Tatzeitpunkt unbestrittenermassen vorliegende schwere psychische Störung des Beschwerdeführers weiter fortbesteht und ihm keine hinreichenden Bewährungsaussichten bezüglich Sexualstraftaten gestellt werden können. Mangels günstiger Prognose seien die Voraussetzungen für eine bedingte Entlassung nicht erfüllt (vgl. angefochtener Entscheid S. 8).
2.4.2. Entgegen der Ansicht des Beschwerdeführers sei sodann davon auszugehen, dass durch die Fortführung der Massnahme der Gefahr weiterer, mit seiner psychischen Störung in Zusammenhang stehender Verbrechen oder Vergehen begegnet werden könne (vgl. angefochtener Entscheid S. 8 f.).
2.4.3. Auch die Verhältnismässigkeit der Massnahme sei vorliegend zu bejahen. Die Massnahme des Beschwerdeführers sei ihm Jahr 1999 durch eine Flucht und einen Rückfall unterbrochen worden, wobei dieser Rückfall die schwerste bisher begangene Straftat darstelle. Die Massnahme habe vor der Flucht 8 Monate gedauert und werde mit dem erstinstanzlichen Beschluss des Strafgerichts Basel-Stadt vom 22. Januar 2021 bis zum 31. Januar 2023, mithin im Ergebnis (gerechnet ab Überstellung des Beschwerdeführers in der Schweiz per 5. September 2011) auf eine Gesamtdauer von 11 Jahren und rund 5 Monaten verlängert. Die langjährige Dauer stelle eine empfindliche Freiheitsbeschränkung dar. Dieser stehe indes ein eminentes öffentliches Interesse an der Verhütung schwerer Rückfälle gegenüber, bestehe doch weiterhin ein deutlich überdurchschnittliches Rückfallrisiko für erneute ähnliche Sexualdelikte. Im Weiteren könne aufgrund der kürzlich erfolgten Verlegung in die JVA St. Johannsen nicht nur die vom Gutachter PD Dr. med. B._ empfohlene Psychotherapie und eine allfällige Medikation weitergeführt, sondern auch Lockerungsversuche durchgeführt werden, die zu einer günstigen Entwicklung beitragen und gemäss Gutachter innerhalb der nächsten 5 Jahre noch zu einer wesentlichen Verbesserung der Legalprognose führen können. Insofern sei die Behandlung im Interesse der öffentlichen Sicherheit und der Spezialprävention fortzusetzen. Zwar habe der Beschwerdeführer zu Recht vorgebracht, dass die Vollzugsbehörde mit seiner Versetzung in eine offene Massnahmenvollzugsanstalt zu lange zugewartet habe. Die lange Massnahmendauer sei in erster Linie jedoch darauf zurückzuführen, dass seine Störung nicht leicht zu behandeln sei und die Behandlung zahlreiche Entwicklungsschritte voraussetze, die dem Beschwerdeführer nicht immer leicht fallen würden. Insgesamt erweise sich die Massnahme noch als verhältnismässig. Mit Blick auf eine mögliche, künftige Versetzung in ein Wohn- und Arbeitsexternat und unter Beachtung des Verhältnismässigkeitsprinzips erscheine eine relativ kurze Dauer der Kontrollfrist von zwei Jahren als sachgerecht (vgl. angefochtener Entscheid S. 10 f.).
2.5.
2.5.1. Die vorinstanzlichen Erwägungen geben zu keiner Kritik Anlass. Im psychiatrischen Gutachten vom 3. September 2018 (Strafakten act. 1150 ff.; nachfolgend: Gutachten) diagnostizierte PD Dr. med. B._ beim Beschwerdeführer eine Kombination von narzisstischer Persönlichkeitsstörung (ICD-10: F60.8) und dissozialer Persönlichkeitsstörung (ICD-10: F60.2), inkl. einer sogenannten Pseudologia phantastica (Drang zum Lügen und Übertreiben), eine zwanghafte sexuelle Verhaltensstörung (bzw. compulsive sexual behavior disorder, ICD-11: 6C72) sowie sexuell sadistische Tendenzen (vgl. Gutachten S. 144 ff.). Diese Diagnosen wurden von therapeutischer Seite nicht in Frage gestellt und im jüngsten Ergänzungsgutachten von PD Dr. med. B._ vom 31. Dezember 2020 (Strafakten act. 2382; nachfolgend: Ergänzungsgutachten) bestätigt (vgl. Ergänzungsgutachten S. 29, 31 und 49). Dass die beiden Gutachten den fachlichen Standards nicht entsprechen würden oder nicht schlüssig seien, macht der Beschwerdeführer zu Recht nicht geltend. Es sind keine Gründe ersichtlich, welche ein Abweichen von der gutachterlichen Diagnose rechtfertigen würden. Die Vorinstanz durfte gestützt auf die Expertisen von PD Dr. med. B._ ohne Weiteres davon ausgehen, dass der Beschwerdeführer nach wie vor an einer psychischen Störung leidet.
2.5.2. Ferner ist nachvollziehbar, dass die Vorinstanz die im Gutachten und im Ergänzungsgutachten diagnostizierte Störung als schwer im Sinne von <ref-law> qualifiziert hat:
Dem Beschwerdeführer ist beizupflichten, dass sich die forensische Relevanz einer psychischen Störung nicht in erster Linie von der Diagnose, sondern vom Ausmass der Störung ableitet (Urteil 6B_1067/2020 vom 5. Mai 2021 E. 1.7). Die Schwere der psychischen Störung entspricht im Prinzip dem Ausmass, in welchem sich die Störung in der Tat spiegelt (Deliktrelevanz). Die Störung muss als vorherrschende Ursache der Delinquenz erscheinen. Die rechtlich geforderte Schwere ergibt sich mit anderen Worten aus der Intensität des Zusammenhangs zwischen der (nach medizinischen Kriterien erheblich ausgeprägten, vorab zweifelsfrei festgestellten) Störung und der Straftat (<ref-ruling> E. 3.5.6 mit Hinweisen; Urteil 6B_828/2019 vom 5. November 2019 E. 1.2.3).
Wie in der Beschwerde zutreffend vorgebracht wird, wurde dem Beschwerdeführer in den Führungs- und Therapieverlaufsberichten der JVA Solothurn bzw. der Psychiatrischen Dienste C._ sowie in verschiedenen früheren Gutachten zwar ein positiver Vollzugsverlauf bescheinigt und ihm gewisse Fortschritte in der deliktsrelevanten Entwicklung attestiert. Auch PD Dr. med. B._ anerkennt in seinem Ergänzungsgutachten, unter Bezugnahme auf die vorhandenen Führungs- und Therapieverlaufsberichte sowie älteren gutachterlichen Ausführungen (vgl. Ergänzungsgutachten S. 2 ff.), dass der Beschwerdeführer eine gewisse Krankheitseinsicht entwickelt hat und einige Fortschritte verzeichnen konnte (vgl. Ergänzungsgutachten S. 33 ff. und 46 f.). So führt er aus, dass es dem Beschwerdeführer offensichtlich weiterhin besser als früher gelungen sei, "sein grosses Bedürfnis nach Anerkennung, Aufmerksamkeit und Zuwendung i.d.R. adäquat [zu] stillen und damit sein Selbstwertgefühl zu stabilisieren" (vgl. Ergänzungsgutachten S. 33). Insofern lasse sich eine "Abnahme bzw. Konsolidierung der erreichten Fortschritte sowohl bzgl. der narzisstischen wie dissozialen Persönlichkeitszüge attestieren" (vgl. Ergänzungsgutachten S. 33 f.). Des Weiteren gebe es unter den "aktuellen Bedingungen" keine "konkreten Belege", dass die zwanghaft sexuelle Verhaltensstörung und die sexuell sadistischen Tendenzen noch bestehen würden (vgl. Ergänzungsgutachten S. 37). Der Gutachter bescheinigt dem Beschwerdeführer damit zweifelsohne einen positiven Massnahmenverlauf. Dabei ist jedoch zu berücksichtigen, dass die gutachterlichen Feststellungen zu den Fortschritten allesamt im Kontext der stark strukturierenden, unterstützenden und kontrollierenden Bedingungen des geschlossenen Massnahmenvollzugs stehen (vgl. etwa Ergänzungsgutachten S. 34). Wie intrinsisch motiviert, tiefgreifend und tragfähig die beim Beschwerdeführer beobachteten Veränderungen sind und ob sich die psychischen Störungen wirklich dauerhaft entaktualisiert haben, lässt sich gemäss dem jüngsten Gutachten von PD Dr. med. B._ erst bei Erprobung mit grösseren Freiheitsgraden verlässlich beurteilen (vgl. Ergänzungsgutachten S. 37 und 46 f.). Insofern wird sich noch weisen müssen, ob die festgestellten Fortschritte auch ausserhalb der engen Strukturen des geschlossenen, hochgesicherten Vollzugs Bestand haben, was im Übrigen auch der Beschwerdeführer anzuerkennen scheint (vgl. Beschwerde S. 14 f.). Dies gilt umso mehr, als dass "Patienten mit Persönlichkeitsstörungen, insbesondere mit dissozialen Zügen", gemäss den überzeugenden Ausführungen von PD Dr. med. B._, "unter institutionellen Bedingungen mit hoher äusserer Strukturierung, Begrenzung und Kontrolle häufig sehr viel weniger auffällig sind als in Freiheit, insbesondere wenn weniger impulsive, sondern eher manipulative Züge im Vordergrund stehen", wie dies beim Beschwerdeführer der Fall sei (vgl. Gutachten S. 176). Mithin sprechen die dem Beschwerdeführer attestierten Fortschritte für sich genommen nicht gegen das Vorliegen einer schweren psychischen Störung im Sinne von <ref-law>.
Trotz der von ihnen konstatierten positiven Entwicklung halten die psychiatrischen Dienste C._ und der Gutachter PD Dr. med. B._ denn auch dafür, dass vom Beschwerdeführer nach wie vor eine deutlich erhöhte bzw. eine deutlich überdurchschnittliche Rückfallgefahr für erneute, gravierende Sexualdelikte ausgeht (vgl. Austrittsbericht vom 23. Dezember 2020, Strafakten act. 2372 ff. S. 4; Ergänzungsgutachten S. 40, 48 und 52). Gemäss dem Gutachter sei "bei einer Beibehaltung des bisherigen Massnahmenvollzugs ohne weitere erfolgreiche Erprobungen in unbegleiteten Lockerungen über einen längeren Zeitraum, sondern Entlassung in Freiheit zum 31.1 2021 [sogar] mit einem besonders hohen Rückfallrisiko zu rechnen" (vgl. Ergänzungsgutachten S. 49 f.). Zu erwarten wären "erneut gewalttätige Übergriffe auf fremde oder nur flüchtig bekannte erwachsene Frauen, auch unter Anwendung von Bedrohung mit einer Waffe, inkl. oraler und vaginaler Penetration" (vgl. Ergänzungsgutachten S. 41 und 49). Aufgrund der betrügerischen und manipulativen Verhaltensweisen des Beschwerdeführers bestehe weiterhin eine hohe Dringlichkeit von Betreuung und Kontrolle (vgl. Ergänzungsgutachten S. 40 und 48). Ausgehend von dieser prognostischen Beurteilung, welche unter anderem auf "der zugrunde liegenden, überdauernden und nur schwer zu behandelnden Kombination von narzisstischer und dissozialer Persönlichkeitsstörung sowie zwanghafter sexueller Verhaltensstörung mit sexuell sadistischen Tendenzen und der weiterhin mangelnden Offenheit und Transparenz [des Beschwerdeführers] bzgl. seines Umgangs mit Sexualität und Intimbeziehungen" basiert (vgl. Ergänzungsgutachten S. 40) und mit Blick auf den funktionalen Begriff der schweren psychischen Störung, der auf die Rückfallprävention auszurichten ist, kann davon ausgegangen werden, dass die psychischen Störungen (zumindest unter gelockerten Bedingungen) nach wie vor verhaltenswirksam sind und durfte die Vorinstanz das Fortbestehen einer schweren psychischen Störung ohne Verletzung von Bundesrecht bejahen. Die nach dem Ergänzungsgutachten von PD Dr. med. B._ ergangenen Vollzugsberichte der JVA St. Johannsen vom 12. Januar 2021 (Strafakten act. 2422 ff.) und 18. Juni 2021 (Akten Appellationsgericht Basel-Stadt act. 9) stehen dieser Auffassung nicht entgegen.
2.5.3. Dass die Vorinstanz hinsichtlich des Vorliegens einer schweren psychischen Störung ihrer Begründungspflicht nicht nachgekommen sei und das rechtliche Gehör des Beschwerdeführers verletzt habe, ist im Übrigen nicht ersichtlich. Nach der bundesgerichtlichen Rechtsprechung genügt es, wenn sich die betroffene Person über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann. In diesem Sinne muss das Gericht wenigstens kurz die Überlegungen nennen, von denen es sich leiten liess und auf welche es seinen Entscheid stützt (<ref-ruling> E. 5.2; <ref-ruling> E. 3.2.4; je mit Hinweisen). Diesen Vorgaben kommt die Vorinstanz nach.
2.6.
2.6.1. Was sodann die Wirksamkeit der therapeutischen Massnahme betrifft, ist nicht zu beanstanden, wenn die Vorinstanz davon ausgeht, dass sich der Gefahr weiterer Taten mit der Fortführung der stationären Massnahme begegnen lasse. Sie schliesst sich dabei ohne Willkür der Beurteilung von PD Dr. med. B._ an, wonach eine weitere Behandlung, bestehend aus einer Kombination von Psychotherapie, allfälliger Medikation und behutsamen, schrittweise auszubauenden und kontrollierten Vollzugslockerungen (vgl. zu den therapeutischen Empfehlungen Ergänzungsgutachten S. 42 ff.) die Legalprognose des Beschwerdeführers, bei positivem Verlauf der Lockerungen, innerhalb der nächsten fünf Jahre wesentlich verbessern würde (vgl. Ergänzungsgutachten S. 51). Der Gutachter schätzt die weitere Behandlung des Beschwerdeführers ausdrücklich als "nicht aussichtslos" ein (vgl. Ergänzungsgutachten S. 51). Inwiefern die Vorinstanz gehalten gewesen wäre, von der gutachterlichen Auffassung abzurücken, ist nicht ersichtlich. Was der Beschwerdeführer gegen die vorinstanzlichen Erwägungen vorbringt, überzeugt nicht.
2.6.2. Unbehelflich ist zunächst die Behauptung, sämtliche Therapeuten und Therapeutinnen wie auch die Gutachter seien übereinstimmend zum Schluss gekommen, dass das mit ihm Erreichbare erreicht worden sei und keine weiteren relevanten rückfallrisikosenkenden Therapieeffekte mehr zu erwarten seien. Entgegen der vom Beschwerdeführer vertretenen Meinung, kann den von ihm genannten Therapieverlaufsberichten der Psychiatrischen Dienste C._ vom 18. Mai 2017 (Strafakten act. 917 ff.), 27. März 2018 (Strafakten act. 1080 ff.) und 26. März 2019 (Strafakten act. 1592 ff.) nicht entnommen werden, dass es an der erforderlichen Wirksamkeit der Massnahme fehle. Die darin wiedergegebenen therapeutische Einschätzung, wonach die IQ-Abklärungen und die neuropsychologische Testung eine grundsätzliche Limitierung der psychotherapeutischen Behandelbarkeit gezeigt habe, psychotherapeutisch ausgeschöpft sei, was in diesem Setting und mit den kognitiven Limiten des Beschwerdeführers erreicht werden könne und man bezüglich Fortschritte und Entwicklungen am Ende der Fahnenstange angekommen sei, bezog sich allein auf eine Fortführung der Massnahme im damals bestehenden geschlossenen Setting der JVA Solothurn. Mit anderen Worten befanden die Therapeuten nicht die stationäre therapeutische Massnahme an sich für aussichtslos beziehungsweise ungeeignet, die Rückfallgefahr für weitere, mit der psychischen Störung des Beschwerdeführers in Zusammenhang stehende Taten, zu beeinflussen, sondern erachteten die bisherige Ausgestaltung der Massnahme als nicht mehr zielführend. Entsprechend haben sich die Psychiatrischen Dienste C._ in ihren Berichten auch explizit für eine Veränderung der therapeutischen Rahmenbedingungen ausgesprochen, von einer bedingten Entlassung jedoch klar abgeraten (vgl. etwa Therapieverlaufsbericht der Psychiatrischen Dienste C._ vom 27. März 2018, Strafakten act. 1080 ff. S. 7 f.; Therapieverlaufsbericht der Psychiatrischen Dienste C._ vom 26. März 2019, Strafakten act. 1592 ff. S. 6 f.).
2.6.3. In dieselbe Richtung gingen auch die an der Verhandlung des Appellationsgerichts des Kantons-Basel Stadt vom 19. September 2019 gemachten Ausführungen von Dr. D._, Leiter der Psychiatrischen Dienste C._. So hat dieser anlässlich seiner Befragung dargelegt, dass der Beschwerdeführer deutlich mehr Erprobungsfelder brauche, als ihm die JVA Solothurn bieten könne und erklärt, dass er die Beibehaltung des geschlossenen, hochgesicherten Settings nicht mehr als sinnvoll erachte, dem Beschwerdeführer ausserhalb der JVA Solothurn aber weitere Fortschritte zuzutrauen seien (vgl. Verhandlungsprotokoll vom 19. September 2019, Strafakten act. 1892 ff. S. 7 und 9 ff.). Folglich hat auch Dr. D._ die Therapierbarkeit des Beschwerdeführers nicht verneint, sondern sich lediglich für einen anderen Therapierahmen ausgesprochen.
2.6.4. Nichts für die beschwerdeführerische Auffassung ableiten lässt sich ferner mit dem Vorbringen, dem Gutachten von PD Dr. med. B._ lasse sich nicht entnehmen, dass mit der Massnahme noch konkret auf die Verbesserung des Gesundheitszustands des Beschwerdeführers eingewirkt werden könne. Der Beschwerdeführer scheint bei dieser Rüge das Ziel der stationären therapeutischen Massnahmen zu verkennen. Diese bezwecken in erster Linie die Reduktion des Rückfallrisikos beziehungsweise die Vermeidung oder Verminderung künftiger Straftaten, was grundsätzlich mit der Behandlung und damit der Besserung des Täters erreicht werden soll. Eine Besserung des Täters beziehungsweise eine Verbesserung dessen Gesundheitszustands interessiert das Strafrecht jedoch grundsätzlich nur insoweit, als sich diese im Erlöschen der Gefährlichkeit des Täters auswirkt, sich also auf den Schutz der Öffentlichkeit vor weiterer Delinquenz bezieht (<ref-ruling> E. 3.5.3; <ref-ruling> E. 3.7; je mit Hinweisen). Lässt sich dieses Ziel durch eine Therapie erreichen, welche die Störung des Täters lediglich mittelbar behandelt, ist dies vom Massnahmenzweck gedeckt (Urteil 6B_643/2018 vom 5. September 2018 E. 1.6.3). Die vom Gutachter PD Dr. med. B._ skizzierten therapeutischen Empfehlungen umfassen sowohl die Fortführung der Psychotherapie und der medikamentösen Behandlung als auch die Gewährung von Vollzugslockerungen, welche bei positivem Verlauf (keine deliktsrelevanten Auffälligkeiten, grössere Offenheit und Transparenz, weiterhin gute Behandlungscompliance etc.) schrittweise zu erweitern seien (vgl. Ergänzungsgutachten S. 42 ff. und 50 f.). Die Lockerungen sollten jeweils inhaltlich und formal therapeutisch vor- und nachbereitet werden (inkl. emotionaler Reaktionen, sexueller Phantasien und Wünsche etc.) (vgl. Ergänzungsgutachten S. 44). Das vom Gutachter vorgeschlagene Vorgehen eröffnet dem Beschwerdeführer neue Übungsfelder und ermöglicht ihm die Erprobung und Festigung seiner bereits erreichten Fortschritte. Die empfohlenen Vollzugslockerungen erscheinen damit als Bestandteil der Behandlung mit dem Ziel, die Legalprognose des Beschwerdeführers zu verbessern. Inwiefern die Fortführung der therapeutischen Massnahme nicht geeignet sein sollte, dieses Ziel zu erreichen, erschliesst sich nicht. Daran vermag auch das beschwerdeführerische Vorbringen, er sei sowohl erschöpft wie auch therapiemüde und habe aufgrund des verzögerten Vollzugsverlaufs Motivationsschwierigkeiten, nichts zu ändern. Motivationseinbrüche deuten nicht zwingend auf eine mangelnde Massnahmenfähigkeit hin. Eine Aussichtslosigkeit der Massnahme infolge fehlender Therapiewilligkeit ist vorliegend weder dargetan noch ersichtlich.
2.7.
2.7.1. Schliesslich hält auch die vorinstanzliche Beurteilung, die Verlängerung der stationären therapeutischen Massnahme erweise sich noch als verhältnismässig, vor Bundes- und Verfassungsrecht stand.
Die Dauer der Massnahme bestimmt sich nach den massnahmenrechtlichen Kriterien und nicht nach Art und Dauer der ausgesprochenen Strafe (vgl. E. 2.2.3 hiervor; <ref-ruling> E. 2.3). Indessen gewinnt der Freiheitsanspruch des Betroffenen bei langandauernder Unterbringung an Gewicht. Je länger ein Freiheitsentzug gedauert hat, umso strengere Anforderungen sind an die Art und Wahrscheinlichkeit künftiger Straftaten zu stellen (<ref-ruling> E. 3.2).
Vorliegend befindet sich der Beschwerdeführer seit rund 20 Jahren im Vollzug und steht eine Verlängerung der Massnahme bis zum 31. Januar 2023, mithin eine Verlängerung der Massnahme auf eine Gesamtdauer von rund 11 1/2 Jahren, zur Diskussion. Zudem ist zu berücksichtigen, dass sich der Beschwerdeführer bis vor kurzem in einem geschlossenen Setting befand, seinem therapeutischen Bedürfnis in der Vergangenheit teils nicht hinreichend Rechnung getragen und mit seiner Versetzung in die offene Massnahmenvollzugsanstalt JVA St. Johannsen zu lange zugewartet wurde (vgl. angefochtener Entscheid S. 11 mit Verweis auf das Urteil des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht vom 15. Juli 2020, Strafakten act. 2247 ff.). Der Eingriff in die Freiheitsrechte des Beschwerdeführers wiegt vor diesem Hintergrund zweifelsohne schwer.
2.7.2. Wie die Vorinstanz zu Recht festhält, stehen dieser Freiheitsbeschränkung jedoch erhebliche öffentliche Interessen gegenüber. Die vom Beschwerdeführer begangenen Sexualstraftaten gehen mit einer Verletzung hochwertiger Rechtsgüter einher und sind als schwere Delikte zu werten. Die Rückfallgefahr für ähnliche Sexualdelikte, d.h. gewalttätige Übergriffe auf fremde oder nur flüchtig bekannte erwachsene Frauen, auch unter Anwendung von Bedrohungen mit einer Waffe, inklusiver oraler und vaginaler Penetration, wird von PD Dr. med. B._ und den Psychiatrischen Dienste C._ - trotz bisheriger positiver Entwicklung im Massnahmenvollzug - als deutlich überdurchschnittlich bzw. deutlich erhöht beurteilt (vgl. E. 2.5.2 hiervor). Dass PD Dr. med. B._ bei seiner Prognose bloss belastende oder statische Faktoren berücksichtigt hätte, trifft nicht zu. Die Vorinstanz durfte bei ihrer Beurteilung gestützt auf die gutachterlichen und therapeutischen Ausführungen von einer hohen Wahrscheinlichkeit weiterer schwerer Straftaten ausgehen. Der Beschwerdeführer vermag diese Erkenntnis nicht als bundesrechtswidrig auszuweisen, indem er pauschal behauptet, das zukünftige Verhalten eines Menschen lasse sich nie zuverlässig voraussagen oder geltend macht, ein Mensch könne sich in 20 Jahren verändern, insbesondere wenn er von einer jahrelangen therapeutischen Intensivbehandlung profitieren konnte.
Inwiefern die heimliche Kontaktaufnahme des Beschwerdeführers mit einer jungen Praktikantin in der JVA Solothurn im Januar 2020 und der Fund eines MP3-Players mit pornographischen Bildern vom Gutachter, den Therapeuten oder der Vorinstanz falsch eingeordnet worden wäre, ist des Weiteren nicht ersichtlich. Der Beschwerdeführer legt in der Beschwerde nur dar, wie diese Ereignisse seines Erachtens zu würdigen gewesen wären. Seine Ausführungen beschränken sich auf eine appellatorische Kritik, auf welche nicht einzutreten ist. Dass die Erwägungen der Vorinstanz, wonach aufgrund verschiedener Ereignisse (darunter die heimliche Kontaktaufnahme zu einer Praktikantin) ein Klärungsbedarf betreffend die Rückfallgefahr des Beschwerdeführers bestanden habe, bundesrechtswidrig sein sollten, ist nicht erkennbar. Weiterungen dazu erübrigen sich.
Auch lässt sich nicht sagen, dass die Massnahme "einzig aufgrund der Untätigkeit der Vollzugsbehörde verlängert werden" müsste bzw. der Beschwerdeführer bei Umsetzung früherer Urteile "bereit für die bedingte Entlassung oder im Lockerungsvollzug zumindest ein grosses Stück weiter" wäre. Der Beschwerdeführer ergeht sich mit diesen Ausführungen in reiner Spekulation. Die Vorinstanz durfte unter Hinweis auf die schlüssigen Gutachten von PD Dr. med. B._ davon ausgehen, dass sich die Störung des Beschwerdeführers nicht leicht behandeln lasse und zahlreiche Entwicklungsschritte voraussetze, die dem Beschwerdeführer nicht immer leicht fallen würden. Ihre Auffassung, wonach die lange Massnahmendauer in erster Linie auf diese Umstände zurückzuführen sei und dem Versetzungsverfahren in dieser Hinsicht kein allzu grosses Gewicht beigemessen werden könne, ist nicht zu beanstanden. Jedenfalls bringt der Beschwerdeführer nichts vor, was diese Feststellungen als willkürlich ausweisen würde.
2.7.3. Mit Blick auf das eminente öffentliche Interesse am Schutz der sexuellen Integrität und angesichts des Umstandes, dass aufgrund der am 24. November 2020 erfolgten Verlegung des Beschwerdeführers in die JVA St. Johannsen nun die Möglichkeit besteht, neben der empfohlenen Psychotherapie und einer allfällige Medikation auch Lockerungsversuche durchzuführen, welche gemäss dem Gutachter PD Dr. med. B._ zu einer günstigen Entwicklung der Legalprognose beitragen können, erscheint die Verlängerung der Massnahme um 2 Jahre als verhältnismässig. Daran vermag die vom Beschwerdeführer geäusserte Kritik an der gegenwärtigen Vollzugsplanung nichts zu ändern. Diese bildet nicht Gegenstand des vorliegenden Verfahrens (<ref-law>). Der vom Beschwerdeführer im Verfahren vor Bundesgericht neu eingereichte Vollzugsplan vom 8. September 2021 datiert zudem aus der Zeit nach dem angefochtenen Entscheid und ist als echtes Novum unbeachtlich (<ref-law>; <ref-ruling> E. 1.2; <ref-ruling> E. 3.2.2.2; je mit Hinweisen).
3.
Die Voraussetzungen der Verlängerung der stationären therapeutischen Massnahme um 2 Jahre sind erfüllt. Auf den Eventualantrag des Beschwerdeführers, er sei statt der Abweisung des Gesuchs auf Verlängerung der Massnahme innerhalb einer vom Gericht vorzugebenden Übergangsfrist bedingt zu entlassen, ist nicht einzutreten. Diese Entscheidung liegt in der Kompetenz der Vollzugsbehörde und kann vom Bundesgericht nicht vorweggenommen werden (vgl. <ref-law>; Urteile 6B_542/2017 vom 18. Juli 2017 E. 3; 6B_360/2012 vom 13. August 2012 E. 4) Gegenstand des angefochtenen Entscheids und damit des vorliegenden Verfahrens ist einzig die Verlängerung der stationären therapeutischen Massnahme um zwei Jahre.
4.
Der Beschwerdeführer beantragt eine angemessene Entschädigung für die ungerechtfertigte Haft seit dem 31. Januar 2021 und begründet dies mit der Aufhebung des vorinstanzlichen Entscheids. Da es bei diesem Entscheid bleibt, ist auf sein Begehren nicht einzutreten.
5.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung ist gutzuheissen. Seine Bedürftigkeit ist ausgewiesen und seine Beschwerde war nicht von vornherein aussichtslos. Es sind daher keine Kosten zu erheben. Der Rechtsvertreterin des Beschwerdeführers ist aus der Bundesgerichtskasse eine Entschädigung auszurichten (Art. 64 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
3.
Es werden keine Gerichtskosten erhoben.
4.
Der Rechtsvertreterin des Beschwerdeführers, Rechtsanwältin Sandra Sutter-Jeker, wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 3'000.-- aus der Bundesgerichtskasse ausgerichtet.
5.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Dreiergericht, schriftlich mitgeteilt.
Lausanne, 28. März 2022
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Jacquemoud-Rossari
Die Gerichtsschreiberin: Rohrer