Sachverhalt:
A.
A.a. Der aus Angola stammende A._ (geb. 1984) reiste am 17. September 1999 in die Schweiz ein und stellte erfolglos ein Asylgesuch. Am 4. August 2003 heiratete er B._ und erhielt am 6. August 2003 eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. In der Folge wurde seine Aufenthaltsbewilligung mehrmals verlängert.
Am 19. August 2008 wurde die Ehe geschieden. Mit Beschluss des Migrationsamtes vom 13. August 2009 wurde A._ aufgrund des Vertrauensschutzes eine eigenständige Aufenthaltsbewilligung erteilt, welche vom ehemaligen Bundesamt für Migration (heute: Staatssekretariat für Migration SEM) am 13. Oktober 2009 genehmigt wurde.
A.b. Am 4. Januar 2009 kam A.C._ (italienische Staatsangehörige), Tochter des A._ und der B.C._ (geb. 1984; italienische Staatsangehörige) zur Welt.
Am 20. März 2011 kam A.D._, Tochter des A._ und der B.D._ (geb. 1990; schweizerische Staatsangehörige) zur Welt.
A.c. Vom 1. Februar 2012 bis 29. März 2012 befand sich A._ aufgrund des Tatverdachts der sexuellen Handlungen mit Kindern, des Verabreichens gesundheitsgefährdender Stoffe an Kinder sowie der Wiederhandlung gegen das Betäubungsmittelgesetz in Untersuchungshaft.
Mit Urteil des Strafgerichts des Kantons Basel-Stadt vom 6. November 2012 wurde er zu einer bedingten Freiheitsstrafe von 18 Monaten mit einer Probezeit von zwei Jahren sowie zu einer Busse in der Höhe von Fr. 200.-- wegen mehrfacher sexueller Handlungen mit Kindern (<ref-law> [SR 311.0]), mehrfachen Verabreichens gesundheitsgefährdender Stoffe an Kinder (<ref-law>), mehrfacher Vergehen nach <ref-law> (SR 812.121) und mehrfacher Übertretung nach <ref-law> verurteilt. Weiter wurde er dazu verurteilt, den beiden Opfern jeweils eine Genugtuung in der Höhe von Fr. 2'000.-- zu leisten. Dieses Urteil wurde vom Appellationsgericht Basel-Stadt am 20. Mai 2014 bestätigt.
Eine dagegen erhobene Beschwerde hiess das Bundesgericht mit Urteil vom 7. Mai 2015 teilweise gut und wies die Sache zur neuen Strafzumessung an das Appellationsgericht Basel-Stadt zurück. Im Übrigen wies das Bundesgericht die Beschwerde ab, soweit es darauf eintrat (Urteil 6B_899/2014). In der Folge bestätigte das Appellationsgericht mit Urteil vom 29. Oktober 2015 das erstinstanzliche Urteil des Strafgerichts Basel-Stadt vom 6. November 2012 im Schuldpunkt und verurteilte A._ zu einer bedingten Freiheitsstrafe von 17 Monaten mit einer Probezeit von zwei Jahren und zu einer Busse in der Höhe von Fr. 200.--.
A.d. A._ ist zudem wie folgt strafrechtlich in Erscheinung getreten:
- Strafbefehl der Staatsanwaltschaft Zürich-Limmat vom 13. Februar 2008: bedingte Geldstrafe von zehn Tagessätzen zu Fr. 80.-- und Busse von Fr. 1'000.-- wegen Fahrens in fahrunfähigem Zustand, einfacher Verletzung von Verkehrsregeln und Fahrens ohne die erforderlichen Kontrollschilder;
- Strafverfügung der Staatsanwaltschaft Solothurn vom 23. April 2008: Busse von Fr. 60.-- wegen Überschreitens der signalisierten Höchstgeschwindigkeit;
- Strafbefehl des Strafbefehlsrichters des Kantons Basel-Stadt vom 28. Oktober 2009: bedingte Geldstrafe von zehn Tagessätzen zu Fr. 100.-- mit einer Probezeit von zwei Jahren und Busse in der Höhe von Fr. 700.-- wegen Widerhandlung gegen das Betäubungsmittelgesetz, Fahrens ohne Führerausweis oder trotz Entzug, Widerhandlung gegen das Strassenverkehrsgesetz und Übertretung der Verkehrsregelnverordnung;
- Strafbefehl vom 20. Februar 2012 der Staatsanwaltschaft des Kantons Basel-Stadt: Busse in der Höhe von Fr. 600.-- wegen Fahrens in fahrunfähigem Zustand;
- Strafbefehl der Staatsanwaltschaft des Kantons Basel-Stadt vom 29. August 2012: Busse von Fr. 80.-- wegen mehrfacher einfacher Verletzung der Verkehrsregeln;
- Strafbefehl der Staatsanwaltschaft des Kantons Basel-Stadt vom 4. Oktober 2012: Busse von Fr. 40.-- wegen einfacher Verletzung der Verkehrsregeln.
A.e. Vom 1. Februar 2013 bis 31. Juli 2014 wurde A._ von der Sozialhilfe Basel-Stadt unterstützt.
Am 31. Mai 2014 kam A.E._, Tochter des A._ und der B.E._ (geb. 1989; schweizerische Staatsangehörige) zur Welt.
B.
B.a. Mit Verfügung vom 6. Juni 2016 verlängerte das Migrationsamt des Kantons Basel-Stadt die Aufenthaltsbewilligung von A._ nicht, wies ihn aus der Schweiz und dem Schengenraum weg und entzog einem allfälligen Rekurs die aufschiebende Wirkung. Mit Zwischenentscheid vom 11. Juli 2016 stellte das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt die aufschiebende Wirkung des von A._ erhobe-nen Rekurses wieder her.
Am 1. September 2017 teilte A._ auf Nachfrage dem Departement mit, dass er am 1. Juni 2017 F._ (geb. 1981; spanische Staatsangehörige) in Basel geheiratet habe. Diese habe in der Schweiz kein Aufenthaltsrecht, jedoch in Spanien.
B.b. Am 7. März 2019 kam in Lörrach (Deutschland) A.G._, Sohn des Rekurrenten und der in Deutschland wohnhaften B.G._ (geb. 1988; spanische Staatsangehörige) zur Welt.
B.c. Mit Entscheid vom 22. April 2020 wies das Departement den gegen die Verfügung des Migrationsamts vom 6. Juni 2016 erhobenen Rekurs von A._ ab. Den dagegen erhobenen Rekurs an den Regierungsrat des Kantons Basel-Stadt überwies das Präsidialdepartement mit Schreiben vom 13. Mai 2020 dem Verwaltungsgericht zum Entscheid.
Mit Urteil vom 2. Dezember 2020 wies das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, Dreiergericht, den Rekurs ab.
C.
Mit Eingabe vom 25. Januar 2021 reicht A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht ein. Er beantragt, das Urteil des Appellationsgerichts Basel-Stadt als Verwaltungsgericht vom 2. Dezember 2020 sei vollumfänglich aufzuheben und das Migrationsamt sei anzuweisen, ihm die Aufenthaltsbewilligung zu verlängern bzw. ihm eine Aufenthaltsbewilligung zu erteilen. Ebenfalls aufzuheben sei die angeordnete Wegweisung aus dem Schengenraum. Eventualiter sei das angefochtene Urteil vollumfänglich aufzuheben und die vorliegende Streitsache zur Neubeurteilung an das Appellationsgericht zurückzuweisen. Die zuständigen Behörden seien anzuweisen, dem Beschwerdeführer die Aufenthaltsbewilligung zu verlängern bzw. zu erteilen. Subeventualiter sei das angefochtene Urteil vollumfänglich aufzuheben und die vorliegende Streitsache zur Neubeurteilung an das Migrationsamt des Kantons Basel-Stadt zurückzuweisen.
In verfahrensrechtlicher Hinsicht beantragt er, es sei ihm ein Replikrecht auf eine allfällige Vernehmlassung der Beschwerdegegner und/ oder der Vorinstanz zu gewähren.
Das Appellationsgericht und das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt schliessen auf Abweisung der Beschwerde. Das Migrationsamt des Kantons Basel-Stadt und das Staatssekretariat für Migration SEM lassen sich nicht vernehmen.
Der Beschwerdeführer hat repliziert.

Erwägungen:
1.
1.1. Gemäss <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumen (vgl. <ref-ruling> E. 2.1; <ref-ruling> E. 1.1.1).
Der Beschwerdeführer ist Vater von drei in der Schweiz geborenen und hier lebenden minderjährigen Töchtern. Ob die Tochter A.C._ (italienische Staatsangehörige) über ein gefestigtes Anwesenheitsrecht in der Schweiz verfügt, lässt sich dem angefochtenen Urteil nicht entnehmen. Die Töchter A.D._ und A.E._, deren Mütter Schweizer Bürgerinnen sind, besitzen indessen von Gesetzes wegen das Schweizer Bürgerrecht (vgl. Art. 1 Abs. 1 lit. b des Bundesgesetzes über Erwerb und Verlust des Schweizer Bürgerrechts vom 29. September 1952 [Bürgerrechtsgesetz, BüG; SR 141.0]) und verfügen somit über ein gefestigtes Anwesenheitsrecht in der Schweiz, sodass sich der Beschwerdeführer in Bezug auf seine Beziehung zu ihnen in vertretbarer Weise auf den Schutz seines Familienlebens i.S.v. <ref-law> und 8 EMRK berufen kann.
Zudem hat der Beschwerdeführer, der sich seit mehr als 20 Jahren in der Schweiz aufhält, einen potenziellen Anspruch auf Erteilung bzw. Verlängerung seiner Aufenthaltsbewilligung gestützt auf den Schutz seines Privatlebens (<ref-law> und Art. 8 EMRK; vgl. <ref-ruling> E. 3.8 und 3.9). Ob der Bewilligungsanspruch tatsächlich besteht, ist praxisgemäss eine Frage der materiellen Beurteilung und keine solche des Eintretens (<ref-ruling> E. 1.1; <ref-ruling> E. 1.1).
Kein Bewilligungsanspruch besteht aufgrund seiner Beziehung zu seiner Ehefrau und seinem in Deutschland lebendem Sohn, da beide über kein Aufenthaltsrecht in der Schweiz verfügen (vgl. vorne, Sachverhalt B.a und B.b).
1.2. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten - vorbehältlich E. 1.3 hiernach - einzutreten (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2, Art. 89 Abs. 1, Art. 90 und Art. 100 Abs. 1 i.V.m. <ref-law>).
1.3. Auf den Antrag des Beschwerdeführers, es sei von der Wegweisung abzusehen, ist nicht einzutreten (<ref-law>). Die Wegweisung ist die normale Folge der Nichtverlängerung bzw. der Verweigerung der Aufenthaltsbewilligung (vgl. <ref-law> [SR 142.20]; bis 31. Dezember 2018: AuG; vgl. auch Urteil 2C_288/2016 vom 13. Oktober 2016 E. 1.2). Die ausländerrechtliche Interessenabwägung muss jedoch bereits sämtliche wesentlichen Aspekte erfassen, wozu auch die Zumutbarkeit der Rückkehr ins Heimatland im bewilligungsrechtlichen Gesamtzusammenhang gehört (vgl. <ref-ruling> E. 4.2).
2.
2.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann insbesondere die Verletzung von Bundes- und Völkerrecht gerügt werden (Art. 95 lit. a und b BGG). Bei der Prüfung wendet das Bundesgericht das Recht von Amtes wegen an (<ref-law>; <ref-ruling> E. 4.4.5) und verfügt es über volle Kognition (<ref-law>; <ref-ruling> E. 2). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht (<ref-law>; <ref-ruling> E. 1.7.2; <ref-ruling> E. 2.2).
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die tatsächlichen Feststellungen der Vorinstanz nur berichtigen oder ergänzen, sofern sie offensichtlich unrichtig sind oder auf einer anderen Rechtsverletzung im Sinne von <ref-law> beruhen (<ref-law>). Eine Sachverhaltsrüge ist substanziiert vorzubringen; auf rein appellatorische Kritik an der Sachverhaltsdarstellung bzw. Beweiswürdigung geht das Gericht nicht ein (<ref-ruling> E. 2.3; <ref-ruling> E. 10.1).
3.
Der Beschwerdeführer beanstandet zunächst die Dauer des vorinstanzlichen Verfahrens und macht in diesem Zusammenhang eine Verletzung des Grundsatzes von Treu und Glauben (Art. 5 Abs. 3 und Art. 9 BV) sowie seines rechtlichen Gehörs (<ref-law>) geltend.
3.1. Er bringt sinngemäss vor, die mehrjährige Verfahrensverschleppung deute darauf hin, dass die Vorinstanzen in seinem Aufenthalt in der Schweiz kein wesentliches Sicherheitsrisiko erblickt hätten. Zudem hätten sich diese widersprüchlich verhalten, indem sie seinem Rekurs die aufschiebende Wirkung erteilt und später argumentiert hätten, das öffentliche Interesse an seiner Wegweisung überwiege seine privaten Interessen an einem Verbleib in der Schweiz. Schliesslich habe seine Rekursbegründung infolge Zeitablaufs jegliche Aktualität verloren, weshalb das Verfahren grundlegend neu durchzuführen sei.
3.2. Der in Art. 9 und 5 Abs. 3 BV verankerte Grundsatz von Treu und Glauben verleiht einer Person Anspruch auf Schutz des berechtigten Vertrauens in behördliche Zusicherungen oder sonstiges, bestimmte Erwartungen begründendes Verhalten der Behörden, sofern sich dieses auf eine konkrete, den betreffenden Bürger berührende Angelegenheit bezieht (<ref-ruling> E. 6.1; <ref-ruling> E. 4.1; je mit Hinweisen). Vorausgesetzt ist, dass die Person, die sich auf Vertrauensschutz beruft, berechtigterweise auf diese Grundlage vertrauen durfte und gestützt darauf nachteilige Dispositionen getroffen hat, die sie nicht mehr rückgängig machen kann (<ref-ruling> E. 2.3 und E. 2.5.1; <ref-ruling> E. 8.1; <ref-ruling> E. 4.1).
3.2.1. Zunächst ist festzuhalten, dass die Vorinstanz eine Verletzung des Rechtsverzögerungsverbots durch das Departement aufgrund der knapp vierjährigen Dauer des Rekursverfahrens bejahte (vgl. E. 2.3.1 des angefochtenen Urteils). Wie das Appellationsgericht indes zu Recht erwog, kann der Beschwerdeführer aus der langen Verfahrensdauer keinen Anspruch auf Verlängerung seiner Aufenthaltsbewilligung ableiten. Ebensowenig wurden dadurch berechtigte Erwartungen geschaffen, dass eine Nichtverlängerung der Aufenthaltsbewilligung nicht mehr ernsthaft zur Diskussion stünde (vgl. auch Urteil 2C_906/2017 vom 7. Mai 2018 E. 3.2).
Sodann kann aus dem Umstand, dass das Departement die aufschiebende Wirkung wiederhergestellt habe, nicht geschlossen werden, dass vom Beschwerdeführer keine Gefahr für die öffentliche Sicherheit und Ordnung (mehr) ausgehe. Nach der Rechtsprechung ist das Interesse eines Ausländers, der sich seit längerem im Land aufhält, an einem vorläufigen Verbleiben in der Schweiz - während der Dauer des Verfahrens um eine Aufenthaltserlaubnis - in der Regel grösser als die Interessen an einem sofortigen Wegweisungsvollzug. Vorbehalten bleiben besondere Gründe von einem gewissen Gewicht, die im Einzelfall die Nichtgewährung der aufschiebenden Wirkung rechtfertigten (vgl. Urteil 2C_604/2014 vom 31. Oktober 2014 E. 2.5; vgl. auch E. 2.3.2 des angefochtenen Urteils). Hinweise darauf, dass im Falle des Beschwerdeführers derartige Gründe bestanden hätten, liegen nicht vor.
3.2.2. Die Rüge der Verletzung des Grundsatzes von Treu und Glauben erweist sich somit als unbegründet. Im Übrigen ist das Interesse an der Fernhaltung des Beschwerdeführers im Rahmen der Verhältnismässigkeitsprüfung zu beurteilen.
3.3. Gemäss <ref-law> haben die Parteien Anspruch auf rechtliches Gehör. Dazu gehört unter anderem das Recht der Betroffenen, an der Erhebung wesentlicher Beweise mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen (<ref-ruling> E. 2.2; <ref-ruling> E. 2.1; <ref-ruling> E. 2.2; je mit Hinweisen).
3.3.1. Die Vorinstanz erwog, der Beschwerdeführer habe mit der Rekursbegründung vom 26. Juni 2020 - abgesehen von den Vorwürfen der langen Verfahrensdauer und des Verstosses gegen Treu und Glauben - im Wesentlichen die gleichen Argumente wie mit der Rekursbegründung vom 19. September 2016 vorgebracht. Zudem sei dem anwaltlich vertretenen Beschwerdeführer namentlich mit Verfügung vom 16. Dezember 2019 die Möglichkeit gewährt worden, sich zu den Ergebnissen der aktuellen Abklärungen des Departements zu äussern. Entsprechendes habe er indessen nicht getan, sondern sich darauf beschränkt, in seiner Eingabe vom 4. März 2020 die Ansetzung einer weiteren Frist für die Ergänzung der Rekursbegründung zu verlangen, für den Fall, dass das Migrationsamt seine Verfügung nicht in Wiedererwägung ziehen würde (vgl. E. 3.3.2 des angefochtenen Urteils). Daher erachtete das Appellationsgericht sein Verhalten geradezu als trölerisch.
Das Departement führt in seiner Vernehmlassung an das Bundesgericht aus, es habe den Sachverhalt ab dem 17. Mai 2019 aufgrund der langen Verfahrensdauer umfassend neu abgeklärt. Zudem habe es dem Beschwerdeführer die Möglichkeit gegeben, sich zu den getätigten Abklärungen und zum aktuellen Sachverhalt zu äussern.
3.3.2. Der Beschwerdeführer setzt sich mit den vorinstanzlichen Erwägungen nicht konkret auseinander und zeigt nicht auf, inwiefern diese unzutreffend seien. Ebensowenig bestreitet er die Ausführungen des Departements.
Es kann somit festgehalten werden, dass dem anwaltlich vertretenen Beschwerdeführer am 16. Dezember 2019 sämtliche durch das Departement getätigten Abklärungen zugestellt wurden und ihm die Möglichkeit eingeräumt wurde, sich dazu zu äussern. Es wäre ihm somit möglich gewesen, bereits zu jenem Zeitpunkt Stellung zu nehmen bzw. seine Rekursbegründung vom 19. September 2016 zu ergänzen. Eine Verletzung seines rechtlichen Gehörs (<ref-law>) liegt nicht vor.
4.
Der Beschwerdeführer macht weiter einen Verstoss gegen Art. 3 und 12 des Übereinkommens vom 20. November 1989 über die Rechte des Kindes (KRK; SR 0.107) geltend. Er wirft den Vorinstanzen vor, zu Unrecht auf eine Anhörung seiner Kinder zu seiner beabsichtigten Rückweisung verzichtet zu haben.
4.1. Gemäss Art. 3 KRK ist bei allen Massnahmen, die Kinder betreffen, das Wohl des Kindes vorrangig zu berücksichtigen. Nach Art. 12 Abs. 1 KRK sichern die Vertragsstaaten dem Kind, das fähig ist, sich eine eigene Meinung zu bilden, das Recht zu, diese Meinung in allen das Kind berührenden Angelegenheiten frei zu äussern, und berücksichtigen die Meinung des Kindes angemessen und entsprechend seinem Alter und seiner Reife. Nach Abs. 2 wird dem Kind zu diesem Zweck insbesondere Gelegenheit gegeben, in allen das Kind berührenden Gerichts- oder Verwaltungsverfahren entweder unmittelbar oder durch einen Vertreter oder eine geeignete Stelle im Einklang mit den innerstaatlichen Verfahrensvorschriften gehört zu werden. Dieses Recht gilt grundsätzlich auch in fremdenpolizeilichen Verfahren, so namentlich wenn das Aufenthaltsrecht eines Kindes oder einer für dieses sorgenden Betreuungsperson in Frage steht (vgl. <ref-ruling> E. 3c; Urteile 2C_488/2019 vom 4. Februar 2020 E. 3.1; 2A.450/2006 vom 21. Dezember 2006 E. 4.1). Wenn es sich um eine lebendige und wichtige persönliche Beziehung handelt, kann allenfalls auch die drohende Unterbrechung oder Erschwerung der Kontaktmöglichkeiten mit einem nicht betreuungsberechtigten Elternteil oder sonstigen Familienmitglied die Interessen des Kindes derart berühren, dass diesem aufgrund von Art. 12 Abs. 1 KRK eine Äusserungsmöglichkeit eingeräumt werden muss (Urteile 2A.450/2006 vom 21. Dezember 2006 E. 4.1; 2A.348/2005 vom 21. Oktober 2005 E. 4.4). Das Bundesgericht geht im Sinn einer Richtlinie davon aus, dass die Kinderanhörung grundsätzlich ab dem vollendeten sechsten Altersjahr möglich ist. Indes ist nicht von vornherein ausgeschlossen, dass sich je nach den konkreten Umständen auch die Anhörung eines etwas jüngeren Kindes aufdrängen könnte, etwa wenn von mehreren Geschwistern das jüngste kurz vor dem genannten Schwellenalter steht (vgl. <ref-ruling> E. 1.2.3).
4.2. Art. 12 KRK stellt einen direkt anwendbaren Rechtssatz dar, dessen Verletzung beim Bundesgericht angefochten werden kann (<ref-ruling> E. 6.5 mit Hinweis). Wie sich aus dem Wortlaut von Art. 12 Abs. 2 KRK ergibt, ist allerdings eine persönliche Anhörung nicht in jedem Fall unerlässlich; wenn die Kinder durch ihre Eltern vertreten werden und beider Interessen gleichläufig sind, kann die Ansicht der Kinder auch ohne persönliche Anhörung durch ihre Eltern eingebracht werden, sofern der rechtserhebliche Sachverhalt auch ohne diese Anhörung rechtsgenüglich festgestellt werden kann (<ref-ruling> E. 3.2; <ref-ruling> E. 6.5 mit Hinweisen; Urteil 2C_234/2019 vom 14. Oktober 2019 E. 3.4).
4.3. Vorliegend ist unbestritten, dass der Beschwerdeführer weder sorge- noch obhutsberechtigt ist. Im Zeitpunkt des angefochtenen Urteils waren seine in der Schweiz lebenden Kinder sechs (A.E._), neun (A.D._) und elf (A.C._) Jahre alt. Entgegen der vorinstanzlichen Auffassung (vgl. E. 4.2.2.1 des angefochtenen Urteils) hätte eine Anhörung der drei Kinder grundsätzlich in Betracht gezogen werden können. Gemäss den vorinstanzlichen unbestrittenen Sachverhaltsfeststellungen besteht indes zwischen dem Beschwerdeführer und seiner Tochter A.E._ kein Kontakt, sodass das Appellationsgericht - ohne Art. 12 KRK zu verletzen - zum Schluss gelangen durfte, dass bezüglich dieser Beziehung kein Anhörungsrecht bestehe.
4.4. Dem angefochtenen Urteil kann entnommen werden, dass das Migrationsamt bei den Müttern der drei Töchter mehrmals Auskünfte über das Verhältnis des Beschwerdeführers zu seinen Kindern und zu allfälligen Unterhaltszahlungen eingeholt hat.
4.4.1. Gemäss der Vorinstanz habe sich die Mutter von A.C._ dreimal eingehend schriftlich zur Vater-Kind-Beziehung und zum Kindesunterhalt geäussert, letztmals im November 2019. Die Mutter von A.D._ habe sich zweimal eingehend schriftlich und einmal mündlich zum Vater-Kind-Verhältnis sowie zum Unterhalt geäussert, letztmals im Dezember 2019. Die Mutter von A.E._ habe sich einmal im Juli 2015 schriftlich zu diesen Fragen geäussert.
Sodann geht aus dem angefochtenen Urteil hervor, dass die Mütter mit Schreiben vom 14. Oktober 2019 darauf hingewiesen wurden, dass die Abklärung des Vater-Kind-Verhältnisses im Rahmen des Rekursverfahrens betreffend die Nichtverlängerung der Aufenthaltsbewilligung und die Wegweisung des Beschwerdeführers erfolgen würde (vgl. E. 4.3.1.2 des angefochtenen Urteils). Die Behauptungen des Beschwerdeführers, wonach die beabsichtigte Nichtverlängerung seiner Aufenthaltsbewilligung den Müttern nicht mitgeteilt worden sei, lassen sich aufgrund der Akten somit nicht erhärten.
4.4.2. Die Vorinstanz führt aus, die Mutter von A.C._ habe mit Schreiben vom 15. Juli 2013 geantwortet, sie vertraue dem Beschwerdeführer insbesondere wegen der sexuellen Übergriffe auf junge Frauen nicht mehr (vgl. E. 4.2.2.2 des angefochtenen Urteils). Zuvor habe sie mit Schreiben vom 31. Mai 2012 dem Migrationsamt mitgeteilt, der Beschwerdeführer leiste keinen Unterhalt für seine Tochter und die Unterhaltsbeiträge würden seit dem 1. Januar 2011 vom Kanton Basel-Landschaft bevorschusst (vgl. angefochtenes Urteil, Sachverhalt, S. 3).
Ebenso habe die Mutter von A.D._ dem Migrationsamt mit Schreiben vom 18. Juli 2012 sinngemäss mitgeteilt, der Beschwerdeführer leiste keinen Unterhalt für seine Tochter und die Unterhaltsbeiträge würden vom Kantons Basel-Landschaft bevorschusst. Der Beschwerdeführer sehe seine Tochter nur unregelmässig, wobei sie denke, dass A.D._ gerne mit ihrem Vater zusammen sei (angefochtenes Urteil, Sachverhalt, S. 3). Sodann habe die Mutter von A.D._ im August 2013 erklärt, sie werde dem Beschwerdeführer den Kontakt zu seiner Tochter verbieten, da er seinen Pflichten als Vater nicht nachkomme und weil sie denke, dass die Tochter von ihm nur enttäuscht und verletzt werde. Indessen sei den Antworten der Mutter vom Dezember 2019 - so die Vorinstanz weiter - zu entnehmen, dass der Beschwerdeführer seine Tochter nach einem Kontaktunterbruch von zwei Jahren seit einem halben Jahr ein Mal pro Monat sehe und die Mutter die Treffen unterstütze. Zudem habe sich die Mutter positiv über den Beschwerdeführer und die Beziehung zwischen ihm und der Tochter geäussert (vgl. E. 4.2.2.2 des angefoch-tenen Urteils).
4.5. Der Beschwerdeführer hält dem allgemein entgegen, dass die Mütter der Kinder ihm gegenüber nicht nur gut gesinnt seien und Ihre Angaben zumindest teilweise persönliche Animositäten vermuten liessen. Er setzt sich indessen mit den detaillierten Ausführungen im angefochtenen Urteil nur knapp auseinander und zeigt nicht konkret auf, dass die Interessen der obhutsberechtigten Mütter und jene ihrer Kinder in Bezug auf die Verlängerung seiner Aufenthaltsbewilligung divergieren würden. Konkrete Anhaltspunkte für eine feindselige Einstellung der Mütter gegenüber dem Beschwerdeführer bestehen aufgrund der Erwägungen im angefochtenen Urteil und der Akten nicht. Damit vermag er auch nicht aufzuzeigen, welche zusätzlichen entscheidrelevanten Erkenntnisse durch die Bestellung einer Kindesvertretung hätten gewonnen werden könnten. Folglich ist mit der Vorinstanz davon auszugehen, dass die Interessen der Kinder durch ihre Mütter als gesetzliche Vertreterinnen wirksam vertreten wurden. Eine Anhörung der Kinder wäre unter den gegebenen Umständen nicht erforderlich gewesen.
5.
5.1. Nach Art. 62 Abs. 1 lit. b AuG (in der hier massgebenden Fassung vom 20. März 2015 [AS 2016 2339]) kann die Aufenthaltsbewilligung widerrufen oder nicht verlängert (vgl. <ref-law>) werden, wenn die Ausländerin oder der Ausländer zu einer längerfristigen Strafe verurteilt worden ist. Als längerfristig im Sinne dieser Bestimmung gilt eine Freiheitsstrafe, wenn ihre Dauer ein Jahr überschreitet (<ref-ruling> E. 2.1; <ref-ruling> E. 4.2 und E. 4.5). Dabei spielt es keine Rolle, ob die Strafe bedingt, teilbedingt oder unbedingt ausgesprochen wurde (<ref-ruling> E. 2.1; <ref-ruling> E. 2.1).
Aufgrund der definitiven Verurteilung vom 29. Oktober 2015 zu einer bedingten Freiheitsstrafe von 17 Monaten erfüllt der Beschwerdeführer ohne Weiteres den Widerrufsgrund von Art. 62 Abs. 1 lit. b AuG, was er auch nicht bestreitet. Er macht indessen geltend, die Nichtverlängerung seiner Aufenthaltsbewilligung verletze seinen Anspruch auf Achtung des Privat- und Familienlebens (<ref-law>; Art. 8 Ziff. 1 EMRK) und sei unverhältnismässig (<ref-law>).
5.2. Liegt ein Widerrufsgrund vor, ist landes- wie konventionsrechtlich zu prüfen, ob sich die ausländerrechtliche Fernhaltemassnahme als verhältnismässig erweist (<ref-law>; <ref-law>; Art. 8 Abs. 2 EMRK), was eine Interessenabwägung unter Berücksichtigung aller wesentlichen Umstände des Einzelfalls erfordert (<ref-ruling> E. 2.2). Bei der Prüfung der Verhältnismässigkeit sind namentlich die Art und Schwere der vom Betroffenen begangenen Straftaten und des Verschuldens, der Grad der Integration bzw. die Dauer der bisherigen Anwesenheit in der Schweiz sowie die dem Betroffenen und seiner Familie drohenden Nachteile zu berücksichtigen (<ref-ruling> E. 2.2.1; Urteil 2C_447/2017 vom 10. September 2018 E. 2.2 mit Hinweisen).
Bei schweren Straftaten und bei Rückfall bzw. wiederholter Delinquenz besteht regelmässig ein wesentliches öffentliches Interesse daran, die Anwesenheit einer ausländischen Person zu beenden, welche die Sicherheit und Ordnung in dieser Weise beeinträchtigt (vgl. <ref-ruling> E. 2.4 und 2.5; Urteile 2C_1045/2019 vom 30. Januar 2020 E. 5.3; 2C_641/2019 vom 3. Oktober 2019 E. 3.2) und muss selbst ein geringes Restrisiko weiterer Delinquenz nicht in Kauf genommen werden (<ref-ruling> E. 4.2-4.4, mit Hinweisen). Der Grad der fortbestehenden Bedrohung ist aufgrund des bisherigen Verhaltens abzuschätzen. Die entsprechende Gefahr setzt nicht voraus, dass ein Straftäter mit Sicherheit wieder delinquieren wird; ebensowenig ist (umgekehrt) verlangt, dass überhaupt kein Restrisiko mehr besteht (Urteile 2C_911/2020 vom 15. März 2021 E. 2.3; 2C_270/2015 vom 6. August 2015 E. 4.1 und 4.2). Je schwerer die zu befürchtende bzw. vernünftigerweise absehbare Rechtsgutsverletzung wiegt, umso weniger ist die Möglichkeit eines Rückfalls ausländerrechtlich hinzunehmen (<ref-ruling> E. 5.3; <ref-ruling> E. 4.2; <ref-ruling> E. 4.3.1). Handelt es sich wie vorliegend um ausländische Personen, die nicht in den Anwendungsbereich des FZA (SR 0.142.112.681) fallen, dürfen auch generalpräventive Gesichtspunkte in die Beurteilung einfliessen (vgl. das Urteile 2C_773/2019 vom 5. Dezember 2019 E. 3.3; 2C_636/2017 vom 6. Juli 2018 E. 3.2.5 mit Hinweisen).
5.3. Ausgangspunkt und Massstab für das migrationsrechtliche Verschulden ist die vom Strafrichter verhängte Strafe.
5.3.1. Dem angefochtenen Urteil und den Akten kann entnommen werden, dass der Beschwerdeführer im Alter von 26 Jahren im Zeitraum vom 24. September 2011 bis zum 9. Dezember 2011 (Opfer 1) und vom August 2011 bis zum 8. Oktober 2011 (Opfer 2) mit zwei 15-jährigen Mädchen mehrfachen, teilweise ungeschützten Geschlechtsverkehr hatte, obwohl er wusste, dass sie sich noch im Schutzalter befanden. In der Folge wurde eines der Mädchen ungewollt schwanger und liess das Kind abtreiben. Zudem bot der Beschwerdeführer den beiden Jugendlichen alkoholische Getränke sowie einem der beiden Mädchen Zigaretten und Marihuana an. In seinem Entscheid vom 22. April 2020 führte das Departement unter Hinweis auf das Strafurteil des Appellationsgerichts vom 29. Oktober 2015 aus, dass die sexuellen Handlungen nicht im Rahmen einer Liebesbeziehung stattgefunden, sondern lediglich der Befriedigung der sexuellen Wünsche des Beschwerdeführers und somit rein egoistischen Motiven gedient hätten. Auch habe zwischen dem Beschwerdeführer und den beiden Mädchen aufgrund des Altersunterschieds ein grosses Machtgefälle bestanden. Ebenfalls bezugnehmend auf das erwähnte Strafurteil des Appellationsgerichts erwog die Vorinstanz, dass das Verhalten des Beschwerdeführers von einer enormen Verantwortungslosigkeit zeuge, da er die beiden Mädchen durch den ungeschützten Geschlechtsverkehr den Risiken von Geschlechtskrankheiten und Schwangerschaften ausgesetzt habe (vgl. E. 6.4.2.2 des angefochtenen Urteils).
5.3.2. Die begangenen Straftaten sind gegen die sexuelle Integrität gerichtet und wiegen deshalb besonders schwer (vgl. <ref-ruling> E. 5.2; Urteil 2C_1045/2019 vom 30. Januar 2020 E. 5.5). Seit dem 1. Oktober 2016 würden sie zudem eine obligatorische Landesverweisung nach sich ziehen (vgl. <ref-law>). Zwar findet diese Regelung nicht rückwirkend auf den Beschwerdeführer Anwendung; dennoch darf bei der Interessenabwägung berücksichtigt werden, dass der Verfassungs- bzw. Gesetzgeber namentlich Sexualdelikte als besonders verwerflich erachtet (vgl. Urteile 2C_1045/2019 vom 30. Januar 2020 E. 5.5; 2C_738/2019 vom 19. Dezember 2019 E. 4.2.1; 2C_108/2018 vom 28. September 2018 E. 4.3.3).
Dass die Vorinstanz aufgrund der Art und Schwere der begangenen Sexualdelikte von einem erheblichen ausländerrechtlichen Verschulden ausgegangen ist, ist nicht zu beanstanden, zumal das Strafmass über der Grenze von einem Jahr liegt, welche für die Möglichkeit des Widerrufs der Aufenthaltsbewilligung massgeblich ist (vgl. <ref-ruling> E. 3.4; Urteil 2C_773/2019 vom 5. Dezember 2019 E. 3.4; vgl. E. 6.4.2.2 des angefochtenen Urteils). Daran ändert auch der Umstand nichts, dass der Strafrichter das Verschulden des Beschwerdeführers als mittelschwer eingestuft hatte, zumal Straf- und Ausländerrecht unterschiedliche Zielsetzungen verfolgen und unabhängig voneinander anzuwenden sind: Der Straf- und Massnahmenvollzug hat nebst der Sicherheitsfunktion eine resozialisierende bzw. therapeutische Zielsetzung; für die Fremdenpolizeibehörden steht demgegenüber das Interesse der öffentliche Ordnung und Sicherheit im Vordergrund, woraus sich ein im Vergleich mit den Straf- und Strafvollzugsbehörden strengerer Beurteilungsmassstab ergibt (<ref-ruling> E. 5.2.2). Im Übrigen hat die Vorinstanz unter Hinweis auf den Entscheid des Departements vom 22. April 2020 und das Urteil des Appellationsgerichts vom 29. Oktober 2015 hinreichend begründet, weshalb sie das migrationsrechtliche Verschulden als erheblich eingestuft hat (vgl. E. 6.4.2.2 des angefochtenen Urteils), sodass - entgegen den Behauptungen des Beschwerdeführers - keine Verletzung des rechtlichen Gehörs (<ref-law>) vorliegt.
5.4. Mit Bezug auf die Rückfallgefahr ist folgendes festzuhalten:
5.4.1. Nebst der mehrfachen sexuellen Handlungen mit Kindern erwirkte der Beschwerdeführer im Zeitraum von 2008 bis 2012 sechs Verurteilungen wegen Verkehrsdelikten und zwei Verurteilungen wegen Betäubungsmitteldelikten (vgl. vorne, Sachverhalt A.d). Zwar wiegen diese Straftaten vergleichsweise weniger schwer, doch zeigen sie, dass der Beschwerdeführer Mühe hat, sich an die Rechtsordnung zu halten.
5.4.2. Sodann befand sich der Beschwerdeführer vom 1. Februar 2012 bis 29. März 2012 in Untersuchungshaft. Bis zur Verurteilung vom 29. Oktober 2015 zu einer bedingten Freiheitsstrafe von 17 Monaten mit einer Probezeit von zwei Jahren stand er sodann unter dem Druck des laufenden Strafverfahrens. Nachdem ihm das Migrationsamt mit Schreiben vom 24. Juli 2015 mitgeteilt hatte, dass es beabsichtige, seine Aufenthaltsbewilligung nicht mehr zu verlängern und ihn aus der Schweiz wegzuweisen, stand er unter dem Druck des ausländerrechtlichen Verfahrens.
Wie die Vorinstanz zutreffend ausführt, kann der Beschwerdeführer aus dem Umstand, dass er seit der Begehung der mehrfachen sexuellen Handlungen mit Kindern im Dezember 2011 nicht mehr wesentlich strafrechtlich in Erscheinung getreten ist, vor diesem Hintergrund nichts zu seinen Gunsten ableiten: Praxisgemäss kommt dem Wohlverhalten während strafrechtlichen Probezeiten bzw. unter dem Druck eines hängigen ausländerrechtlichen Verfahrens nur untergeordnete Bedeutung zu. In dieser Zeit wird ein vorbildliches Verhalten erwartet und stellt ein solches keine besondere Leistung dar (Urteile 2C_92/2020 vom 10. Juni 2020 E. 5.3; 2C_488/2019 vom 4. Februar 2020 E. 5.5; vgl. E. 6.4.2.2 des angefochtenen Urteils). Dabei ist festzuhalten, dass die Frage, wie ein allfälliges Wohlverhalten zu gewichten sei - entgegen den Behauptungen des Beschwerdeführers - nicht die Sachverhaltsfeststellung, sondern die rechtliche Würdigung betrifft.
5.4.3. Schliesslich ist darauf hinzuweisen, dass der Beschwerdeführer auch im bundesgerichtlichen Verfahren keine Reue zeigt bzw. versucht, sein Verhalten zu relativieren. So führt er - wie auch im vorinstanzlichen Verfahren - aus, er habe einvernehmliche sexuelle Kontakte mit Bekannten gehabt, welche das Schutzalter von 16 Jahren um wenige Monate bzw. Wochen noch nicht erreicht hätten. Wie die Vorinstanz zu Recht ausführt, deutet dies daraufhin, dass er immer noch nicht eingesehen habe, dass auch einvernehmliche sexuelle Handlungen mit Kindern unter 16 Jahren das Risiko einer Beeinträchtigung der Kinder in ihrer Persönlichkeitsbildung und Sexualentwicklung bergen (vgl. E. 6.4.2.2 des angefochtenen Urteils). Dabei ist nicht entscheidend, ob der Beschwerdeführer (zusätzlich) versucht habe, die beiden Mädchen - wie die Vorinstanz annimmt - zu falschen entlastenden Aussagen zu bewegen, sodass auf die in diesem Zusammenhang erhobene Rüge der willkürlichen Sachverhaltsfeststellung mangels Erheblichkeit für den Ausgang des Verfahrens nicht weiter einzugehen ist.
5.5. Angesichts der konkreten Umstände ist die Vorinstanz zu Recht zum Schluss gelangt, dass weitere Straftaten nicht ausgeschlossen seien (vgl. E. 6.4.2.2 des angefochtenen Urteils). An der Fernhaltung des Beschwerdeführers besteht somit ein erhebliches sicherheitspolizeiliches Interesse.
6.
Das öffentliche Interesse an der Fernhaltung des Beschwerdeführers kann nur durch entsprechend gewichtige private Interessen aufgewogen werden könnte, d.h. es müssen aussergewöhnlich schwerwiegende Umstände gegen eine Wegweisung sprechen.
6.1. Ins Gewicht fällt zunächst die Beziehung des Beschwerdeführers zu seinen drei in der Schweiz lebenden Kindern.
6.1.1. Nach der bundesgerichtlichen Rechtsprechung zu Art. 8 Ziff. 1 EMRK sowie <ref-law> ist die Erteilung einer Aufenthaltsbewilligung an einen - wie vorliegend - weder sorge- noch hauptsächlich betreuungsberechtigten ausländischen Elternteil zur Ausübung seines Besuchsrechts in der Regel nicht erforderlich. Unter dem Gesichtswinkel des Schutzes des Anspruchs auf Familienleben genügt es nach den Umständen, dass der Kontakt zum Kind im Rahmen von Kurzaufenthalten, Ferienbesuchen oder über die modernen Kommunikationsmittel vom Ausland her wahrgenommen werden kann; gegebenenfalls sind die zivilrechtlichen Modalitäten hierfür den ausländerrechtlichen Vorgaben anzupassen (<ref-ruling> E. 5.1; <ref-ruling>5 E. 2.2; Urteile 2C_904/2018 vom 24. April 2019 E. 2.2; 2C_417/2018 vom 19. November 2018 E. 7.1). Ein weitergehender Anspruch fällt nur dann in Betracht, wenn eine in affektiver und in wirtschaftlicher Hinsicht besonders enge Beziehung zum Kind besteht, diese Beziehung wegen der Distanz zum Heimatland des Ausländers praktisch nicht aufrechterhalten werden könnte und das bisherige Verhalten der ausländischen Person in der Schweiz zu keinerlei namhaften Klagen Anlass gegeben hat (vgl. <ref-ruling> E. 5.2; <ref-ruling> E. 5.2; <ref-ruling> E. 6.2; jeweils mit Hinweisen). Dies ist in der Regel nicht der Fall, wenn gegen die ausländische Person, welche sich auf Art. 8 EMRK beruft, fremdenpolizeiliche Entfernungs- und Fernhaltegründe sprechen, insbesondere sie sich massgebliches, strafrechtlich oder fremdenpolizeilich verpöntes Fehlverhalten hat zu schulden kommen lassen (<ref-ruling> E. 5.2.4 mit Hinweisen).
6.1.2. Bezüglich der Tochter A.E._, zu welcher der Beschwerdeführer nach dem Gesagten keinen Kontakt hat (vgl. E. 4.3 hiervor), fehlt es bereits an der Voraussetzung einer besonders engen Beziehung in affektiver Hinsicht. Ob dieses Kriterium, wie die Vorinstanz erwägt, auch in Bezug zu seinen Töchtern A.C._ und A.D._ zu verneinen sei (vgl. E. 6.2.3.2 des angefochtenen Urteils), kann offenbleiben, zumal der Anspruch des Beschwerdeführers auf Verbleib im Land im Hinblick auf die Beziehung zu seinen hier anwesenheitsberechtigten Kindern aufgrund seiner Straffälligkeit ohnehin am Kriterium des klaglosen Verhaltens scheitert.
Zudem ist mit der Vorinstanz davon auszugehen, dass die Voraussetzung der besonders engen Bindung in wirtschaftlicher Hinsicht ebenfalls nicht erfüllt ist. So hat der Beschwerdeführer nach den vorinstanzlichen Erwägungen die geschuldeten Unterhaltsbeiträge für seine Kinder nie freiwillig geleistet. Zwar könne gemäss dem Appellationsgericht nicht ausgeschlossen werden, dass Unterhaltsbeiträge vereinzelt vom kantonalen Sozialamt Basel-Landschaft beim Beschwerdeführer erhältlich gemacht worden seien; zumindest zu einem Grossteil hätten aus den Bemühungen des Sozialamtes jedoch Verlustscheine resultiert (vgl. E. 6.2.3.3 des angefochtenen Urteils). Der Beschwerdeführer bestreitet die vorinstanzlichen Ausführungen nicht und macht auch nicht geltend, dass er in einer anderen Form einen Beitrag am Unterhalt der Kinder geleistet habe, sodass kein Anlass besteht, von den vorinstanzlichen Ausführungen abzuweichen.
6.1.3. Zwar ist davon auszugehen, dass dem Beschwerdeführer die Aufrechterhaltung des persönlichen Kontakts zu seinen Kindern von Angola aus schwer fallen dürfte, doch könnte dieser über die modernen Kommunikationsmittel sowie im Rahmen von Ferienbesuchen gepflegt werden. Konkrete Gründe, weshalb dies nicht der Fall sein sollte, werden nicht geltend gemacht und sind auch nicht ersichtlich.
6.2. Nichts zu seinen Gunsten kann der Beschwerdeführer schliesslich aus seiner langen Anwesenheit in der Schweiz ableiten.
6.2.1. Der Beschwerdeführer lebte im Zeitpunkt des angefochtenen Urteils seit etwas mehr als 20 Jahren in der Schweiz. Das Bundesgericht hat hierzu festgehalten, dass nach einer rechtmässigen Aufenthaltsdauer von rund zehn Jahren regelmässig davon ausgegangen werden könne, dass die sozialen Beziehungen in der Schweiz so eng geworden seien, dass es für eine Aufenthaltsbeendigung besonderer Gründe bedarf; im Einzelfall könne es sich jedoch anders verhalten, wenn die Integration zu wünschen übrig lasse (<ref-ruling> E. 3.9). Angesichts der konkreten Umstände korreliert die lange Aufenthaltsdauer vorliegend nicht mit der wirtschaftlichen und sozialen Integration des Beschwerdeführers.
6.2.2. Gegen eine gelungene Integration in sozialer Hinsicht spricht zunächst seine schwere Delinquenz. Zudem weist er gemäss den unbestrittenen Feststellungen der Vorinstanz eine erhebliche Verschuldung auf. So bestehen gegen ihn Verlustscheine in der Höhe von Fr. 117'958.40.-- (vgl. E. 6.5.2 des angefochtenen Urteils). Der Beschwerdeführer behauptet nicht, dass er diese Schulden abbauen werde, sondern führt insbesondere aus, dass die offenen Verlustscheine zu bedauern seien und dass es sich dabei um viele Jahre alte offene Forderungen handle.
Schliesslich legt der Beschwerdeführer nicht dar, dass er - abgesehen von seinen Kindern - über ein ausgebautes Beziehungsnetz in der Schweiz verfügt. Zwar erwähnt er einen grossen Freundes- und Bekanntenkreis, doch bleibt diese Behauptung unsubstanziiert (vgl. E. 6.3.3 des angefochtenen Urteils). Zudem verfügt er unbestrittenermassen über soziale Bindungen zu anderen Ländern, namentlich zu Deutschland, wo sein Sohn zusammen mit dessen Mutter lebt, sowie zu Spanien, wo sich seine Ehefrau aufhält.
Positiv zu würdigen ist, dass der Beschwerdeführer sprachlich integriert ist und über eine Festanstellung verfügt, die ihm erlaubt, seinen Lebensunterhalt selber bestreiten zu können. Entgegen seiner Auffassung fällt seine berufliche Integration angesichts der verübten Straftaten und seiner auch sonst mangelhaften sozialen Integration vorliegend nicht entscheidend ins Gewicht.
6.3. Eine Rückkehr des Beschwerdeführers in sein Heimatland erscheint auch zumutbar: Vor seiner Einreise in die Schweiz lebte er 15 Jahre dort und verbrachte somit die persönlichkeitsprägenden Kinder- und Jugendjahre in seiner Heimat. Zudem hielt er sich nach den unbestrittenen Feststellungen der Vorinstanz in den Jahren 2005 (einen Monat), 2011, 2015, 2016 (rund zwei Monate) und 2018 (knapp einen Monat) in Angola auf und verbrachte gemäss eigenen Angaben im vorinstanzlichen Verfahren einmal im Jahr seine Ferien dort, wo sein Vater, seine Schwester, sein Bruder und seine Mutter leben (vgl. E. 6.3.2 des angefochtenen Urteils). Es kann somit angenommen werden, dass er nach wie vor mit der Sprache und den kulturellen Gepflogenheiten seines Heimatlands vertraut ist.
Zwar ist davon auszugehen, dass die Rückkehr des Beschwerdeführers in sein Heimatland mit gewissen Schwierigkeiten verbunden sein wird, doch erscheint diese nicht unmöglich. Die in der Schweiz erworbene Berufserfahrung sowie die in Angola abgeschlossene Malerlehre werden ihm bei der beruflichen Wiedereingliederung zugute kommen (vgl. E. 6.6.2 des angefochtenen Urteils). Zudem könnten ihn seine dort lebenden Angehörigen bei seinen Reintegrationsbemühungen unterstützen. Schliesslich kann er aus seinen Ausführungen zu seinen Beziehungen im Schengenraum (Deutschland und Spanien) keinen Bewilligungsanspruch in der Schweiz ableiten (vgl. E. 1.1 hiervor), sodass darauf nicht weiter einzugehen ist.
6.4. Im Ergebnis kann festgehalten werden, dass aufgrund der Art und Schwere der begangenen Straftaten und der nicht auszuschliessenden Rückfallgefahr ein grosses öffentliches Interesse an der Beendigung des Aufenthalts des Beschwerdeführers besteht. Dieses überwiegt sein privates Interesse an seinem weiteren Verbleib in der Schweiz. Die Nichtverlängerung der Aufenthaltsbewilligung des Beschwerdeführers verletzt daher weder Bundes- noch Konventionsrecht und erweist sich als verhältnismässig (Art. 13 Abs. 1 und <ref-law>; Art. 8 Ziff. 2 EMRK; 96 Abs. 1 AIG). Da der Grundsatz der Verhältnismässigkeit nicht verletzt ist, hätte das Migrationsamt den Beschwerdeführer auch nicht zuerst verwarnen müssen (vgl. <ref-law>; vgl. Urteile 2C_911/2020 vom 15. März 2021 E. 4.4; 2C_787/2018 vom 11. März 2019 E. 3.4.1; 2C_656/2018 vom 13. Dezember 2018 E. 2.6; 2C_1018/2016 vom 22. Mai 2017 E. 3.2).
7.
Nach dem Gesagten erweist sich die Beschwerde in öffentlich-rechtlichen Angelegenheiten als unbegründet und ist abzuweisen, soweit darauf einzutreten ist.
Bei diesem Ausgang des Verfahrens wird der unterliegende Beschwerdeführer kostenpflichtig (<ref-law>). Eine Parteientschädigung ist nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Verfahrenskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, Dreiergericht, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 29. Juli 2021
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Die Gerichtsschreiberin: Ivanov