Sachverhalt:
A.
Das Strafgericht des Kantons Basel-Stadt sprach A._ am 25. Februar 2019 des Verbrechens gegen das Betäubungsmittelgesetz durch grosse Gesundheitsgefährdung sowie bandenmässige Tatbegehung schuldig. Von den Vorwürfen der mehrfachen rechtswidrigen Einreise und des mehrfachen rechtswidrigen Aufenthalts sprach es ihn frei. Das Strafgericht verurteilte A._ zu 4 1⁄4 Jahren Freiheitsstrafe, unter Anrechnung der Haft sowie des vorzeitigen Strafvollzugs. Es verwies ihn zudem für 10 Jahre des Landes und ordnete die Ausschreibung im Schengener Informationssystem (SIS) an.
Auf Berufung von A._ und Anschlussberufung der Staatsanwaltschaft Basel-Stadt hin erhöhte das Appellationsgericht des Kantons Basel-Stadt die Freiheitsstrafe auf 4 1⁄2 Jahre. Im Übrigen bestätigte es den strafgerichtlichen Entscheid, soweit dieser nicht schon in Rechtskraft erwachsen war.
B.
A._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Appellationsgerichts sei teilweise aufzuheben. Er sei vom Vorwurf des bandenmässigen Verbrechens gegen das Betäubungsmittelgesetz freizusprechen und zu einer bedingten, eventualiter teilbedingten Freiheitsstrafe von 18 Monaten zu verurteilen. Er sei für 5 Jahre des Landes zu verweisen. Von einer Ausschreibung der angeordneten Landesverweisung im Schengener Informationssystem sei abzusehen. Eventualiter sei das Urteil des Appellationsgerichts aufzuheben und die Sache zu neuer Entscheidung an dieses zurückzuweisen. A._ ersucht um unentgeltliche Rechtspflege.

Erwägungen:
1.
1.1. Der Beschwerdeführer wendet sich gegen seine Verurteilung wegen Verbrechens gegen das Betäubungsmittelgesetz durch bandenmässige Tatbegehung. Er sei zu keinem Zeitpunkt in die bandenmässigen Strukturen integriert gewesen und lediglich als Kurier und Werkzeug der Bande tätig gewesen. Er habe das Kokain auf genaue Instruktion und Kontrolle durch die Hintermänner für eine geringfügige finanzielle Entschädigung von den Niederlanden in die Schweiz transportiert. In subjektiver Hinsicht seien ihm die genauen Ziele der Hintermänner und ihre interne Organisation nicht bekannt gewesen, weshalb er sich nicht damit habe identifizieren können.
1.2. Die Vorinstanz erklärt den Beschwerdeführer des Verbrechens gegen das Betäubungsmittelgesetz mit Gefährdung der Gesundheit vieler Menschen sowie des bandenmässigen Verbrechens gegen das Betäubungsmittelgesetz schuldig (angefochtenes Urteil, S. 13). Sie erwägt, der Beschwerdeführer habe insgesamt knapp 5 kg qualifiziert hochwertiges Kokaingemisch in die Schweiz transportiert (angefochtenes Urteil, E. 2.1 S. 6). Er habe in einem Zeitraum von zweieinhalb Monaten für eine hoch organisierte international agierende Bande fünf Transporte ausgeführt. Diese Transporte seien ohne Mitwirkung der Zentrale in Amsterdam, ohne Anweisungen für sichere Wege, ohne Leitung via Mobiltelefonate zum Depothalter in Basel und ohne Entschädigungsabwicklung via weitere Bandenmitglieder nicht durchführbar gewesen. Der Beschwerdeführer sei einer ständigen Kontrolle durch die Hinterleute unterlegen, habe aber vom Sicherheitsdispositiv bei der sorgfältigen Planung der Reisen profitiert. All diese Umstände seien ihm bekannt gewesen. Er habe bewusst als Teil der Organisation agiert und entsprechende Entschädigung erwartet. Wer im Bewusstsein dieser Struktur die Transporte ausführe und ohne in flagranti ertappt zu werden auch weitere ausgeführt hätte, sei ein Bandenmitglied und wolle dies sein (angefochtenes Urteil, E. 2.2 S. 7 f.).
1.3. Gemäss <ref-law> wird der Täter mit einer Freiheitsstrafe nicht unter einem Jahr, womit eine Geldstrafe verbunden werden kann, bestraft, wenn er als Mitglied einer Bande handelt, die sich zur fortgesetzten Ausübung des unerlaubten Betäubungsmittelhandels zusammengefunden hat.
Nach der Rechtsprechung ist Bandenmässigkeit anzunehmen, wenn zwei oder mehr Täter sich mit dem ausdrücklich oder konkludent geäusserten Willen zusammenfinden, inskünftig zur Verübung mehrerer selbstständiger im Einzelnen noch unbestimmter Straftaten zusammenzuwirken. Das Qualifikationsmerkmal der Bande setzt gewisse Mindestansätze einer Organisation, etwa Rollen- oder Arbeitsteilung, und eine Intensität des Zusammenwirkens in einem Masse voraus, dass von einem stabilen Team gesprochen werden kann, auch wenn dieses nur kurzlebig ist. In subjektiver Hinsicht muss sich der Täter des Zusammenschlusses und der Zielrichtung der Bande bewusst sein. Sein Vorsatz muss die die Bandenmässigkeit begründenden Tatumstände umfassen. Bandenmässige Tatbegehung ist nur anzunehmen, wenn der Wille der Täter auf die gemeinsame Verübung einer Mehrzahl von Delikten gerichtet ist (Urteil 6B_1302/2020 vom 3. Februar 2021 E. 2.4.2, zur Publikation vorgesehen; <ref-ruling> E. 2 und E. 3.4; <ref-ruling> E. 2b; je mit Hinweisen).
1.4. Dem Beschwerdeführer ist nicht zu folgen, wenn er vorbringt, er sei nicht in die bandenmässigen Strukturen integriert gewesen. Laut nicht beanstandeter und für das Bundesgericht verbindlicher Sachverhaltsfeststellung transportierte er in einem Zeitraum von mehreren Monaten für eine hoch organisierte Bande wiederholt Kokain von den Niederlanden nach Basel. Dies stellt einen bedeutenden Tatbeitrag dar. Ferner hätte er, so die Vorinstanz, auch weitere Transporte ausgeführt, wäre er nicht ertappt worden. Somit war er offensichtlich Teil eines arbeitsteilig operierenden Teams, welches zur Ausübung eines fortgesetzten Betäubungsmittelhandels zusammengefunden hatte. Die als Kurier beschränkte Funktion des Beschwerdegegners steht dem nicht per se entgegen. Gleiches gilt für die Umstände, wonach er weisungsabhängig gewesen und engmaschig begleitet worden sei, sowie für die Höhe seiner Entschädigung. Diese Aspekte berücksichtigt die Vorinstanz zu Recht im Rahmen der Strafzumessung und der Wertung seines Tatverschuldens (vgl. E. 2.2 hiernach). Unbehelflich sind sodann die Vorbringen des Beschwerdeführers, die genauen Ziele der Hintermänner und ihre interne Organisation seien ihm nicht bekannt gewesen. Detailliertes Wissen über die Organisation, welches über deren Mindestansätze und Zielrichtung hinausgeht, ist für die Erfüllung des subjektiven Tatbestands nicht erforderlich. Dass sein Wille auf die entscheidwesentliche gemeinsame Verübung einer Mehrzahl von Delikten gerichtet war, bestreitet er demgegenüber nicht. Demzufolge verletzt die vorinstanzliche Qualifikation des Beschwerdeführers als Bandenmitglied kein Bundesrecht.
2.
2.1. Der Beschwerdeführer kritisiert sodann die vorinstanzliche Strafzumessung. Die Vorinstanz verletze ihr Ermessen. Sie verkenne, dass die Sicherheit der Reiseroute nicht ihm, sondern dem Schutz der Hintermänner gedient habe. Er sei auch weisungsabhängig von diesen und als Kurier auf der hierarchisch untersten Stufe gewesen. Er habe keinerlei Entscheidungsbefugnisse gehabt. Für das objektive Tatverschulden erscheine eine Einsatzstrafe von 18 Monaten als angemessen. Weiter habe die Vorinstanz zu Unrecht seine finanzielle Notlage sowie besondere Strafempfindlichkeit verneint. Aus seiner 13 Jahre zurückliegenden Verurteilung in Frankreich lasse sich keine besondere Unbeeindruckbarkeit ableiten. Auch die Anlastung seiner Schulterschmerzen gegenüber der Polizei sei entgegen der Ansicht der Vorinstanz keine bewusst falsche Schuldzuweisung.
2.2. Die Vorinstanz erwägt, das Tatverschulden des Beschwerdeführers sei nicht mit demjenigen eines Bodypackers zu vergleichen. Er habe sich ohne gesundheitliche Risiken und dank der guten Organisation auf sicheren Reiserouten bewegen können. Es sei um keine Gelegenheitsdelinquenz gegangen. Vielmehr habe er eine gewisse Vertrauensstellung genossen, sei er doch innert kurzer Zeit mit dem Transport von hochwertigem und kostbarem Stoff betraut worden. Dass ihn ein geeignetes und reiseerfahrenes Bandenmitglied sofort hätte ersetzen können, sei eher unwahrscheinlich. Hingegen treffe es zu, dass der Beschwerdeführer weisungsabhängig gewesen sei und die Kurierdienste unter engmaschiger Begleitung der Hintermänner ausgeführt habe. Das objektive Tatverschulden wiege daher mittelschwer.
Beim subjektiven Tatverschulden sei ein finanzielles Motiv vorgelegen. So habe der Beschwerdeführer in zweieinhalb Monaten rund Euro 10'000.-- verdient, abzüglich maximal Fr. 2'500.-- Reisekosten. Das sei für einen in Spanien lebenden Familienvater mit unregelmässigem Erwerbseinkommen zweifellos ein beträchtlicher Beitrag an die Lebenshaltungskosten. Dass eine eigentliche finanzielle Notlage bestanden habe, sei nicht klar ersichtlich. Der Beschwerdeführer lebe seit 1998 in Spanien. Er habe eine gute Ausbildung in Nigeria als Elektroingenieur abgeschlossen. In Spanien habe er in einer chemischen Fabrik auf Stundenlohnbasis gearbeitet. Er habe einzig während zwei Monaten Arbeitslosengeld bezogen. Er besitze ein eigenes Auto. Damit unterscheide sich seine finanzielle Lage nicht von derjenigen einer Vielzahl anderer in Spanien lebender Personen. Seine Passeinträge von Mai bis Oktober 2017 belegten intensive Reisen in Länder wie die Türkei via Griechenland, Äthiopien und Moçambique. Diese hätten offensichtlich finanziert werden können. Von einer eigentlichen Notlage sei daher nicht auszugehen. Alles in allem rechtfertige es sich angesichts des mittelschweren Verschuldens, eine Einsatzstrafe von 4 Jahren Freiheitsstrafe festzulegen.
Bei der Täterkomponente seien noch die Vorstrafen aus Dänemark und Frankreich zu beachten. Trotz massiver Vorwarnungen und Verbüssung von 20 Monaten in Frankreich und rund 2 Monaten in Dänemark hätten ihm jene Strafen offenbar keinen Eindruck gemacht. Das Urteil aus Frankreich datiere vom 4. April 2007 und laute auf 2 Jahre Gefängnis. Es sei dem Beschwerdeführer nach <ref-law> noch immer entgegenzuhalten. Eine besondere Strafempfindlichkeit wegen der familiären Situation sei zu verneinen. Der Beschwerdeführer habe sich zu den Reisen in Kenntnis seiner Verpflichtungen gegenüber seiner Ehefrau und seinen drei Kindern entschlossen. Dass die 17-jährige Tochter in der Zwischenzeit von zuhause ausgerissen sein soll und die Ehefrau eine Fehlgeburt erlitten habe, mag belastend sein. Was die gesundheitliche Situation anbelange, so berufe er sich darauf, dass er nun Probleme an der rechten Schulter habe, welche er bei der angeblich brutalen Festnahme durch die Polizei verursacht worden seien. Diese These werfe ein besonders ungünstiges Licht auf den Beschwerdeführer. Der eingereichte Arztbericht spreche von chronischer anteriorer Luxationsfraktur. Dies passe zu den Ausführungen des Beschwerdeführers, er habe schon im Jahr 2015 einen Unfall gehabt. Dass nun die seit langem bestehenden Schulterschmerzen und der schlecht verheilte Bruch der Polizei angelastet werden sollten, zeige, dass er taktiere und sich durch Angriff zu verteidigen versuche. Er habe es übrigens verstanden, die Ärzte insofern irrezuführen, als diese vermerkt hätten, es handle sich um eine in Fehlstellung verheilte Luxationsfraktur nach Trauma im April 2018. Die hier manifestierte Gesinnung zeige sich auch in den diversen Einvernahmen. Bewusst falsche Schuldzuweisungen an andere würfen kein gutes Licht auf ihn.
Die Erhöhung der Strafe durch die Vorinstanz um ein halbes Jahr angesichts der Unbeeindruckbarkeit des Beschwerdeführers durch Strafverfahren sei nicht zu beanstanden. Auch seine Eingabe im Berufungsverfahren zeuge nicht von Unrechtsbewusstsein, sondern diene letztlich einer Anklage an die Justiz und Polizei. Ob der Beschwerdeführer das Unrecht seiner Tat, abgesehen von einem Bedauern, dass er dem Schweizer Staat Kosten verursacht habe, bereut habe, sei nicht ersichtlich. Insgesamt erweise sich eine Freiheitsstrafe von 4 1⁄2 Jahren als angemessen (vgl. angefochtenes Urteil, E. 4. S. 9 ff.).
2.3. Das Bundesgericht hat die Grundsätze der Strafzumessung nach <ref-law> wiederholt dargelegt (vgl. z.B. <ref-ruling> E. 5.4 ff. mit Hinweisen). Darauf kann verwiesen werden. Das Sachgericht hat die für die Strafzumessung erheblichen Umstände und deren Gewichtung festzuhalten und seine Überlegungen in den Grundzügen wiederzugeben, so dass die Strafzumessung nachvollziehbar ist. Dabei steht ihm ein erheblicher Ermessensspielraum zu. Das Bundesgericht greift auf Beschwerde hin in die Strafzumessung nur ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn sie von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wesentliche Gesichtspunkte ausser Acht gelassen bzw. in Überschreitung oder Missbrauch ihres Ermessens falsch gewichtet hat (<ref-ruling> E. 1.2; <ref-ruling> E. 6.1.1; 244 E. 1.2.2; <ref-ruling> E. 2.1; <ref-ruling> E. 8.1).
2.4. Die auf 4 1⁄2 Jahre festgesetzte Freiheitsstrafe für die qualifizierte Widerhandlung gegen das Betäubungsmittelgesetz mit einem Strafrahmen von 1 Jahr bis 20 Jahren Freiheitsstrafe (vgl. <ref-law> i.V.m. <ref-law>) ist nicht zu beanstanden. Die Vorinstanz übt ihr Ermessen bei der Strafzumessung pflichtgemäss aus und die Ausführungen des Beschwerdeführers sind nicht geeignet, einen Ermessensmissbrauch aufzuzeigen. So berücksichtigt die Vorinstanz den Aspekt, wonach er weisungsabhängig gewesen sei, bereits strafmindernd. Sein persönliches Risiko bewertet die Vorinstanz überzeugend als geringer im Vergleich zu demjenigen anderer Betäubungsmittelkuriere. Dass die Sicherheitsmassnahmen im Zusammenhang mit der Planung seiner Reiseroute nicht lediglich den weiteren am Betäubungsmittelhandel beteiligten Personen, sondern auch ihm in seiner Funktion als Kurier dienten, lässt sich nicht bestreiten. Auch die vorinstanzlichen Erwägungen zur finanziellen Situation und zur Strafempfindlichkeit des Beschwerdeführers sind nicht zu beanstanden. In den vorinstanzlichen Wertungen der Vorstrafen sowie des Unrechtsbewusstseins des Beschwerdeführers ist ebenso wenig eine Verletzung von Bundesrecht ersichtlich.
3.
3.1. Der Beschwerdeführer beanstandet im Weiteren die Dauer der ausgesprochenen Landesverweisung von 10 Jahren. Es sei ihm eine positive Legalprognose zuzugestehen, weil er sich der Konsequenzen eines Strafverfahrens bewusst sei und er wisse, dass dadurch die Existenz seiner Familie gefährdet werde. Eine Landesverweisung von 5 Jahren sei ausreichend.
3.2. Die Vorinstanz erwägt, die Voraussetzungen der obligatorischen Landesverweisung seien erfüllt. Der Beschwerdeführer habe weder familiäre noch berufliche Verbindungen zur Schweiz. Er habe in Spanien einen Aufenthaltstitel und seine Familie lebe dort. Betäubungsmitteldelikte mit internationalen Transporten im Kilobereich in bandenmässiger Form verletzten die Grundinteressen der internationalen Gemeinschaft. Die Rückfallgefahr sei gross. Der Beschwerdeführer habe einschlägige Erfahrung im Betäubungsmittelhandel. Er sei sprachgewandt und reisegewohnt. Eine Anheuerung für weitere Transporte wäre ohne Weiteres zu erwarten. Die Dauer der Landesverweisung sei auf 10 Jahre zu bemessen. Angesichts des Alters des Beschwerdeführers sei zu erwarten, dass nach Ablauf von 10 Jahren die Gefahr gebannt sei (vgl. angefochtenes Urteil, E. 5. S. 12).
3.3. <ref-law> zufolge verweist das Gericht den Ausländer, der wegen Widerhandlung gegen Art. 19 Abs. 2 oder Art. 20 Abs. 2 des Betäubungsmittelgesetzes verurteilt wird, unabhängig von der Höhe der Strafe für 5 - 15 Jahre aus der Schweiz.
3.4. Die Vorinstanz begründet nachvollziehbar und schlüssig, weshalb sie eine zehnjährige Landesverweisung als angemessen erachtet. Anlässlich ihrer entsprechenden Prüfung weist sie zutreffend darauf hin, dass der Beschwerdeführer keinerlei Beziehungen zur Schweiz hat. Deshalb ist sein Interesse an der von ihm beantragten gesetzlichen Minimaldauer der Landesverweisung ausser Zweifel als tief zu gewichten. Gestützt auf seine einschlägigen früheren Straftaten und seine fortgesetzte Tatbegehung lässt sich entgegen seiner Darstellung zudem eine Rückfallgefahr keineswegs von der Hand weisen. Die Familie als Argument des Beschwerdeführers gegen eine Rückfallgefahr berücksichtigte bereits die Vorinstanz. Sie erwog auch diesbezüglich stichhaltig, dass er sich trotz Kenntnis seiner Verpflichtungen gegenüber seiner Ehefrau und seinen drei Kindern zu seinen Straftaten entschlossen hatte. Dazu äussert sich der Beschwerdeführer nicht. Es liegt im vorliegenden Fall kein Härtefall im Sinne von <ref-law> vor. Im Übrigen wiegt das öffentliche Interesse an der Landesverweisung bei Straftaten gegen das Betäubungsmittelgesetz praxisgemäss besonders schwer (vgl. Urteile 6B_1027/2020 vom 24. Februar 2021 E. 2.2.1; 6B_1424/2019 vom 15. September 2020 E. 2.4.5; 6B_1299/2019 vom 28. Januar 2020 E. 3.3; je mit Hinweisen). Demzufolge überwiegt das öffentliche Fernhalteinteresse das Interesse des Beschwerdeführers an einer möglichst kurzen Landesverweisung deutlich und die Dauer der ausgesprochenen Landesverweisung von 10 Jahren erweist sich, auch mit Blick auf das Tatverschulden und die ausgesprochene Freiheitsstrafe von 4 1⁄2 Jahren, als bundesrechtskonform.
4.
4.1. Der Beschwerdeführer trägt schliesslich vor, die vorinstanzlich vorgesehene Ausschreibung im SIS sei weder erforderlich noch angemessen. Es sei für die Existenz seiner Familie unerlässlich, dass er auch in benachbarten europäischen Ländern nach einer Anstellung suchen könne, sollte er in Spanien keine solche finden. Eine Ausschreibung im SIS führe wohl dazu, dass seine spanische Aufenthaltsbewilligung nicht mehr verlängert werde und er mit seiner Familie dieses Land verlassen müsste. Damit wiegten seine privaten Interessen gegen eine Ausschreibung im SIS viel höher als die öffentlichen Interessen an einer solchen.
4.2. Die Vorinstanz erwägt, angesichts der Natur der zu befürchtenden weiteren Delinquenz sei eine Ausschreibung im SIS gerechtfertigt. Der Beschwerdeführer nehme an einem international oder womöglich sogar interkontinental aufgezogenen Betäubungsmittelhandel teil. Je weniger er sich in europäischen Ländern bewegen könne, umso weniger werde er in Zukunft von Betäubungsmittelbanden angeheuert werden. Dass er zu legalen Zwecken auf Reisen durch europäische Länder angewiesen sei, sei nicht ersichtlich. Reisen in aussereuropäische Länder blieben von dem Eintrag unberührt (angefochtenes Urteil, E. 5. S. 12 f.).
4.3.
4.3.1. Eine Ausschreibung von Drittstaatsangehörigen im Sinne von Art. 3 lit. d der Verordnung (EG) Nr. 1987/2006 des Europäischen Parlaments und des Rates vom 20. Dezember 2006 über die Einrichtung, den Betrieb und die Nutzung des Schengener Informationssystems der zweiten Generation (SIS-II-Verordnung; ABl. L 381 vom 28. Dezember 2006) im SIS darf gemäss dem in Art. 21 SIS-II-Verordnung verankerten Verhältnismässigkeitsprinzip nur vorgenommen werden, wenn die Angemessenheit, Relevanz und Bedeutung des Falles dies rechtfertigen.
Voraussetzung der Ausschreibung im SIS ist eine nationale Ausschreibung, die auf einer Entscheidung der zuständigen nationalen Instanz (Verwaltungsbehörde oder Gericht) beruht (Art. 24 Abs. 1 SIS-II-Verordnung). Die Ausschreibung wird eingegeben, wenn die Entscheidung auf die Gefahr für die öffentliche Sicherheit oder Ordnung oder die nationale Sicherheit gestützt wird, die die Anwesenheit des betreffenden Drittstaatsangehörigen im Hoheitsgebiet eines Mitgliedstaats darstellt (Art. 24 Abs. 2 Satz 1 SIS-II-Verordnung). Das ist insbesondere dann der Fall, wenn die betreffende Person in einem Mitgliedstaat wegen einer Straftat verurteilt wurde, die mit einer Freiheitsstrafe von mindestens einem Jahr bedroht ist (Art. 24 Abs. 2 Bst. a SIS-II-Verordnung), oder wenn gegen sie der begründete Verdacht besteht, dass sie schwere Straftaten begangen hat, oder wenn konkrete Hinweise bestehen, dass sie solche Straftaten im Hoheitsgebiet eines Mitgliedstaats plant (Art. 24 Abs. 2 Bst. b SIS-II-Verordnung).
4.3.2. Die Ausschreibung der Landesverweisung im SIS bewirkt, dass der betroffenen Person die Einreise in das Hoheitsgebiet aller Schengen-Mitgliedstaaten grundsätzlich untersagt ist (vgl. Art. 6 Abs. 1 Bst. d i.V.m. Art. 14 Abs. 1 der Verordnung [EU] Nr. 2016/399 des Europäischen Parlaments und des Rates vom 9. März 2016 über einen Gemeinschaftskodex für das Überschreiten der Grenzen durch Personen [Schengener Grenzkodex], ABl. L 77 vom 23. März 2016 S. 1; vgl. auch Art. 32 Abs. 1 Bst. a Ziff. v der Verordnung [EG] Nr. 810/2009 des Europäischen Parlaments und des Rates vom 13. Juli 2009 über einen Visakodex der Gemeinschaft [Visakodex], ABl. L 243 vom 15. September 2009 S. 1). Die übrigen Schengen-Staaten können die Einreise in ihr Hoheitsgebiet im Einzelfall aus humanitären Gründen oder Gründen des nationalen Interesses oder aufgrund internationaler Verpflichtungen indes dennoch bewilligen (Art. 6 Abs. 5 Bst. c Schengener Grenzkodex; vgl. auch Art. 25 Abs. 1 Bst. a Visakodex). Die Souveränität der übrigen Schengen-Staaten wird insofern durch die in der Schweiz ausgesprochene Landesverweisung, welche ausschliesslich für das Hoheitsgebiet der Schweiz gilt (vgl. <ref-law>), nicht berührt (<ref-ruling> E. 3.2.3 mit Hinweisen).
4.4. Die Ausschreibung des Beschwerdeführers im SIS liegt innerhalb des Ermessens der Vorinstanz. Sie begründet die Ausschreibung damit, dass die Anwesenheit des Beschwerdeführers im Hoheitsgebiet der Schengen-Mitgliedstaaten eine Gefahr für die öffentliche Sicherheit oder Ordnung darstellt. Dies ist insbesondere mit Blick auf Art. 24 Ziff. 2 Bst. a der SIS-II-Verordnung nicht zu beanstanden. Die Strafmassandrohung für die Tat des Beschwerdeführers und ferner auch die gegen ihn ausgefällte viereinhalbjährige Freiheitsstrafe überschreiten die in dieser Bestimmung vorgesehene Mindeststrafandrohung von einem Jahr Freiheitsstrafe deutlich. Das vom Beschwerdeführer geltend gemachte und rein abstrakte Interesse, allenfalls in europäischen Ländern ausserhalb von Spanien nach einer Anstellung suchen zu müssen, wiegt demgegenüber nicht schwer. Die Einschränkungen auf seine Bewegungsfreiheit im Hoheitsgebiet aller Schengen-Mitgliedstaaten als mögliche Folge der Ausschreibung hat er in Kauf zu nehmen. Die Beschwerde ist folglich auch in diesem Punkt abzuweisen.
5.
Die Beschwerde ist abzuweisen. Das Gesuch um unentgeltliche Rechtspflege ist in Anwendung von <ref-law> wegen Aussichtslosigkeit abzuweisen. Die Gerichtskosten sind ausgangsgemäss dem Beschwerdeführer aufzuerlegen (<ref-law>). Der finanziellen Lage des Beschwerdeführers ist mit reduzierten Gerichtskosten Rechnung zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'200.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Dreiergericht, schriftlich mitgeteilt.
Lausanne, 12. März 2021
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Jacquemoud-Rossari
Der Gerichtsschreiber: Weber