Paul Fosu-Mensah speelde in de jeugd van AVV Zeeburgia en AFC Ajax, waar hij na een kruisbandblessure vertrok. Nadat een meniscusblessure ook tijdens een stage bij Fulham FC roet in het eten gooide, sloot hij in 2020 aan bij de jeugd van Vitesse, waar hij een jaar bleef. Na een proefperiode bij het SchotseGreenock Morton FC, sloot hij in 2021 na een proefperiode bij Helmond Sport aan.[3] Hier tekende hij een contract voor één seizoen, met een optie voor een extra jaar. Fosu-Mensah debuteerde in het betaald voetbal op 20 augustus 2021, in de met 3-2 verloren uitwedstrijd tegen MVV Maastricht. Hij kwam in de 83e minuut in het veld voor Jarno Lion. In december 2021 veroverde hij een vaste basisplaats bij Helmond.
Medio 2022 ging hij op het tweede niveau in Roemenië voor ACSM Poli Iasi spelen. In februari 2023 ging hij naar het Noorse Brattvåg IL dat uitkomt in de 2. Divisjon.