Paulo Muñoz Toledo comenzó a tocar el corno a la edad de 12 años,comenzando en el Conservatorio de Música de la Universidad de Chile, con Raúl Silva y más tarde con Edward Brown.
Tres años más tarde, recibió una beca para asistir a un campamento de música de verano en los Estados Unidos. A su regreso, se le pidió que tocara con las secciones de corno de la Orquesta Filarmónica de Santiago, Orquesta Sinfónica Nacional, Orquesta de Cámara de Santiago, etc.
Como miembro de la Orquesta Sinfónica Juvenil Nacional, tocó el Concierto
de Strauss para Trompa y Orquesta Nº 1.
También se desempeñó 4 años como primer corno con la Orquesta Mundial de Juventudes Musicales, tiempo donde también pasó un año estudiando en el Conservatorio de París.
Recibió una beca de los Amigos del Teatro Municipal de Santiago, y luego de ser becado en 1995 por la Fundación Andes, comenzó sus estudios de licenciatura en la Hochschule der Künste Berlin (Colegio de Artes, hoy en día, UdK), con los maestros Sebastian Weigle, Gerd Seifert y privadamente con Ignacio García, siendo este último su mentor. Después de un corto período como “praktikant” en la Ópera Estatal de Berlín (Deutsche Staatsoper), fue aceptado en 1997 en la en 1997 en la prestigiosa Academia de Karajan de la Filarmónica de Berlín, estudiando consu cornista principal, Norbert Hauptman.
Trabajó con la Filarmónica de Berlín junto a grandes directores, como Osawa, Mehta, Barenboim, Haitink y Harding, por nombrar a algunos.
En 1997 y por invitación directa de Claudio Abaddo, se convierte en miembro fundador de la Mahler Chamber Orchestra, puesto que ocupó hasta 2005.
En 1998 comenzó a tocar con la Deutsches Symphonie Orchester Berlin.
Desde 2002 es miembro de la Orquesta de la Tonhalle de Zürich.
En 2003 también tocó con el conocido Ensemble Wien-Berlin.
Ha participado en los festivales de música más importantes de Europa, Asia y América del Norte, como los Proms de Londres, el Pacific Music Festival en Sapporo, el Festival de Salzburgo, el Festival de Aix-en-Provence y el Festival de Lucerna, bajo la dirección de Claudio Abbado.
También es profesor visitante en el conservatorio de música de Zürich, donde prepara a los estudiantes en proyectos orquestales. En 2008-2009 enseñó en la Hochschule fur Musik en Mainz.
Desde hace varios años también ha participado en las actividades de la Brass Academy Alicante.
Mantiene muchos de los lazos con su pasado, actuando regularmente con sus orquestas anteriores, así como en numerosos grupos de cámara, mientras mantiene un papel activo como profesor de corno.