Argentina lead the South American group on 29 points with two qualifiers remaining next month. The top four qualify automatically and the group leaders can now only be overtaken by Colombia and Chile. (Agencies)
"We knew how difficult it is to qualify and this is our reward for all the good work we've been doing," Messi said.
"It wasn't easy to play with the poor state of the pitch but the main thing was to go for our qualification," he added at the Defensores del Chaco stadium.
Captain Messi put his team ahead in the 12th minute at the same venue where Argentina had lost the equivalent qualifier under Diego Maradona four years ago.
Messi converted from the spot after Sergio Aguero was brought down by goalkeeper Roberto Fernandez.
But Paraguay, who began the match with only the slimmest hopes of reaching the fifth-place playoff berth, conjured up a fine equaliser when striker Jose Nunez deflected a left cross past Sergio Romero from a narrow angle six minutes later.
The visitors were soon back on the front foot, however, and Aguero gave Argentina a crucial 2-1 halftime lead in the 32nd minute.
Messi chested down a ball with his back to goal into Aguero's path and the striker nudged it forwards before hitting a low left-footed shot inside the base of the far post.
Winger Angel Di Maria increased Argentina's lead five minutes into the second half, running onto a through ball from playmaker Fernando Gago and shooting home across Fernandez.
Messi's second penalty after he was brought down took his tally as joint top scorer in the qualifiers to 10, equal to Uruguay's Luis Suarez and one ahead of suspended team mate Gonzalo Higuain.
It also took Messi's international tally to 37 in 83 matches, past Hernan Crespo and into second place behind Gabriel Batisuta's 56 in 78.
Paraguay captain Roque Santa Cruz pulled one back in the 85th minute before substitute Maxi Rodriguez, looking to go to a third World Cup tournament with Argentina, rounded off the scoring in the final minute from Di Maria's pass.
Argentina lead the South American group on 29 points with two qualifiers remaining next month. The top four qualify automatically and the group leaders can now only be overtaken by Colombia and Chile.