First I should pacifiy two villages, after this the quest continues and I should kill an unconvertable army.

I never found this army.

The quest-text says something about "perhaps you need to send out troops to patrol the region".

Is this related to the region where I pacified the viallges or the whole map?

I sent out troops everywhere to find this army and ended up with a domination victory...