In another hadith prophet said a person who collected water from well using a shoe in his mouth for a thirsty dog entered paradise.
A man felt very thirsty while he was on the way; he came across a well. He went down the well, quenched his thirst and came out. Meanwhile he saw a dog panting and licking mud because of excessive thirst. He said to himself, "This dog is suffering from thirst as I did." So, he went down the well again and filled his shoe with water and watered it. Allah was pleased with him for that deed and forgave him."
The people with the Messenger of Allah (pbuh) said,
"O Messenger of Allah! Is there a reward for us in serving the animals?" The Prophet (pbuh) said,
"Yes, there is a reward for serving any animate (living being)." [Bukhari, Shirb 9, Wudu 33, Mazalim 23, Adab 27; Muslim, Salam 153, (2244); Muwatta, Sifatun Nabi 23, (2, 929-930); Abu Dawud, Jihad 47, (2550)]
The hadith you stated and above hadith are contradicting compassion for animals.
There might be some harm averted by killing dogs of medinah only. Hence the command. He didn't order a person from iraq kills all dogs of Baghdad