In the eastern city of Multan, hard-line Muslim students burned effigies of Queen Elizabeth II and Rushdie. About 100 students carrying banners condemning the author also chanted, "Kill him! Kill him!"
On Saturday, Britain announced the knighthood for the author of "The Satanic Verses" in an honors list timed for the official celebration of the queen's 81st birthday.
Lawmakers in Pakistan's lower house of parliament on Monday passed a resolution proposed by Minister for Parliamentary Affairs Sher Afgan Khan Niazi, who branded Rushdie a "blasphemer."
"The 'sir' title from Britain for blasphemer Salman Rushdie has hurt the sentiments of the Muslims across the world. Every religion should be respected. I demand the British government immediately withdraw the title as it is creating religious hatred," Niazi told the National Assembly.
Lawmakers voted unanimously for the resolution although one opposition member, Khwaja Asif, said it exposed a contradiction in the government's policy as an ally of Britain in the war on terrorism.
Foreign Ministry spokeswoman Tasnim Aslam said Rushdie's knighthood would hamper interfaith understanding and that Islamabad would protest to London.
"We deplore the decision of the British government to knight him. This we feel is insensitive and we would convey our sentiments to the British government."
Iran on Sunday also condemned the knighthood for Rushdie.
Iran's late spiritual leader, Ayatollah Khomeini, issued a 1989 fatwa, or religious edict, ordering Muslims to kill the author because "The Satanic Verses" allegedly insulted Islam. The threat forced Rushdie to live in hiding for a decade.
The British High Commission in Islamabad defended the decision to honor Rushdie - one of the most prominent novelists of the late 20th century whose 13 books have won numerous awards, including the Booker Prize for "Midnight's Children" in 1981.
"Sir Salman's honor is richly deserved and the reasons for it are self-explanatory," said spokesman Aidan Liddle.