Why “proč” and not “čeho”?
Does it has to do with the difference between "have no reason to fear" (Nemaji se proč bat.) vs. "there is nothing to fear" (Neni se čeho bat)? (please excuse limited diacritics heare)
Why can't I say "Nemají se o co bát."?
That has a different meaning. "bát se o" is "to be afraid for", "to be worried about" "to be concerned about". You are afraid that something bad will happen to the subject or that you will loose it.
Is it possible to use: Nemají důvod ke strachu?
It is not direct enough, "to fear" is an infinitive "bát se", not a noun like in "They have no reason for fear.".