Paz speelde in totaal 21 officiële interlands voor Bolivia in de periode 1999-2005 en scoorde drie keer voor La Verde. Onder leiding van de Argentijnse bondscoach Héctor Veira maakte hij zijn debuut op 25 augustus1999 in de vriendschappelijke thuiswedstrijd tegen Venezuela (0-0) in Sucre, net als Carlos Cárdenas. Hij moest in die wedstrijd plaatsmaken voor Roger Suárez. Paz nam in 2001 met zijn vaderland deel aan de strijd om de Copa América.