The attack took place in Orgun district near the border with Pakistan.
The governor of the province said the intended victims were a district chief and an army officer, both of whom escaped with minor injuries.
Militants linked to the Taleban have carried out a wave of attacks in Afghanistan recently.
Governor Mohammed Akram Akhpelwak said several provincial officials were hurt in the bombing.
He told the Reuters news agency the dead also included members of a militia working alongside US troops in the area.
Nato soldier killed
Sunday's attack is the deadliest since a suicide bombing in Kabul in September killed 16 people, two of them US soldiers.
Separately, Nato forces say they killed at least 50 Taleban fighters in two separate battles in the southern province of Uruzgan on Saturday.
One Nato soldier was also killed, a spokesman for the alliance said.
Villagers in one of the affected areas told the BBC that 12 civilians had been killed in the air strikes but Nato said it could not confirm these claims.
At least another five Taleban rebels have reportedly died in clashes with Nato troops in Kandahar province.
Paktika province in Afganistan
A suicide bomber has killed at least seven people in an attack on a restaurant situated in south-eastern Afghanistan. Twenty people are seriously injured in the attack.

The attack took place in the Urgun district of Paktika province, which shares its border with that of Pakistan.

Governor Mohammed Akram Akhpelwak said that most of those killed are civilians. He added that intention of the attack could have been to target a senior provincial official and an Afghan special forces commander.