Pakistani President Pervez Musharraf has called the killing of two Pakistanis held hostage in Iraq a crime against humanity.
Relatives said the men did nothing wrong
The nation's parliament said it was a "brutal act" that had shocked the entire country.
A videotape from a group calling itself the Islamic Army in Iraq showed the bodies of hostages Azad Hussein Khan and Sajjad Naeem.
In another videotape, militants were shown holding a Somali hostage.
On the tape, broadcast by al-Jazeera on Thursday, militants belonging to al-Qaeda suspect Abu Musab al-Zarqawi's Tawhid and Jihad group threatened to behead the Somali truck driver unless his Kuwaiti employers pulled out of Iraq.
State of shock
A Pakistani foreign ministry spokesman said it had confirmed that the videotape was genuine.
Azad Hussein Khan and Sajjad Naeem, an engineer and driver, were reported missing in Iraq last Friday.
Their kidnappers had threatened to execute them unless their Kuwaiti employers left Iraq.
Foreign ministry spokesman, Masood Khan, said the killings had devastated the families of the victims and the Pakistani nation.
President Musharraf said the captors had "caused harm to humanity and Islam".
Pakistan's charge d'affaires in Baghdad, Muhammad Iftikhar Anjum, urged the kidnappers not to "desecrate" the bodies and to hand them over for proper burial.
The Pakistani government said it would seek compensation from the men's employers.
Azad Hussein Khan's widow (R) and children with his picture
The families in Pakistan-administered Kashmir are said to be in a state of shock.
The government there has declared Friday a day of mourning.
Mohammed Naeem, father of Sajjad, said: "You cannot imagine the agony we are going through."
Mr Khan's brother-in-law, Abdul Razaq, said the Pakistani government should have ruled out sending troops to Iraq.
"If the government of Pakistan had tried, this tragedy could've been averted. The government should have categorically said it would not send troops to Iraq," he said.
Hundreds of people have been visiting the home village of the two men to offer their sympathy.
The BBC's Zaffar Abbas, in Islamabad, says that although a number of foreign hostages have been killed by various groups in Iraq, this is the first incident in which citizens from a Muslim country have been executed by kidnappers.
Another militant group in Iraq is holding seven foreign truck drivers; three Indians, three Kenyans and an Egyptian.
14 April: Fabrizio Quattrocchi, 36, Italian security guard is shot dead
11 May: Nick Berg, 26, US businessman is beheaded
22 June: Kim Sun-il, 33, South Korean translator is beheaded
29 June: Keith Maupin, 20, US soldier is reportedly killed (not confirmed)
14 July: Georgi Lazov, 30, Bulgarian truck driver is beheaded
On Thursday, Indian Prime Minister Manmohan Singh said his government was making "all efforts" to secure the Indian citizens' release.
On Tuesday, Pakistan appealed to the Islamic Army in Iraq to release its citizens saying they had committed no crime.
It denied the group's claim that the two men were working for US forces and said Pakistan had made no commitment to send troops to Iraq.
Last month, a different militant group kidnapped another Pakistani citizen from Baghdad, but the man was freed after a series of appeals.
In recent months, Pakistan has remained under intense pressure from the US to send its troops to Iraq.
Our correspondent says President Musharraf has agreed in principle to consider the move, but he has continued to delay a final decision to avoid a domestic political backlash.
Following the latest incident, it may become extremely difficult for the Pakistani government to send its troops to Iraq, he adds.