I am not sure if I am crazy, but it doesn't sound grammatical to me.
The children, all eight of them, had different unknown fathers.
What's wrong and is there a word or phrase that mean the same thing that would make the sentence sound idiomatic?
There is nothing wrong with the sentence.
Simplifying it into a shorter sentence, you can contrast it with another one:
They had different unknown fathers.
Each of them had a different father. The identity of each of those fathers was unknown.
They had the same unknown father.
They all shared the same father. The identity of the father was unknown.
In both of these sentences, the father or fathers may be unknown to them but known to someone else. Alternatively, something like DNA testing might have proven the fathers to be the same or different.