Erste internationale Erfahrungen sammelte Paulo Herrera im Jahr 2012, als er bei den U23-Südamerikameisterschaften in São Paulo in 49,02 s den achten Platz im 400-Meter-Lauf belegte und mit der peruanischen 4-mal-400-Meter-Staffel in 3:14,18 min die Bronzemedaille hinter den Teams aus Brasilien und Venezuela gewann. Im Jahr darauf schied er bei den Südamerikameisterschaften in Cartagena mit 48,37 s im Vorlauf aus und verpasste anschließend auch bei den Juniorensüdamerikameisterschaften in Resistencia mit 50,53 s den Finaleinzug. 2015 gewann er dann bei den Südamerikameisterschaften in Lima in 3:14,64 min gemeinsam mit Bryan Erazo, Williams García und Luis Saavedra die Bronzemedaille in der 4-mal-400-Meter-Staffel hinter den Teams aus Venezuela und Chile. Im Jahr darauf belegte er bei den U23-Südamerikameisterschaften ebendort in 49,24 s den vierten Platz über 400 m und wurde auch in der 4-mal-400-Meter-Staffel in 3:19,09 min Vierter. 2017 wurde er bei den Juegos Bolivarianos in Santa Marta im Vorlauf über 400 m disqualifiziert und belegte in 53,44 s den fünften Platz über 400 m Hürden. Im Jahr darauf verpasste er bei den Ibero-Amerikanischen Meisterschaften in Trujillo mit 53,71 s den Finaleinzug im Hürdenlauf, gewann aber mit der Staffel in 3:15,59 min die Bronzemedaille hinter den Teams aus Chile und Ecuador. Im Folgejahr klassierte er sich bei den Südamerikameisterschaften in Lima mit 52,86 s auf dem sechsten Platz im Hürdenlauf und gelangte mit der Staffel nach 3:14,28 min auf Rang vier. Anschließend startete er über 400 m Hürden bei den Panamerikanischen Spielen ebendort und schied dort mit 54,09 s im Vorlauf aus.
2013 wurde Herrera peruanischer Meister im 400-Meter-Lauf sowie 2019 über 400 m Hürden.
Peru
