"Alle dyr har sjeler" sort of implies that all animals have several souls. This is what the English sentence says, so the translation is correct in the literal sense.
If you wanted to make common sense, however, you'd probably say "alle dyr har sjel". In Norwegian "sjel" very rarely is inflected in the plural.
That's what I tried to say the last time this sentence showed up, but I was ruled out. In Norwegian it's very uncommon to use plurals for items of which there is only one of per person. Like hearts and souls.