It would be very easy to get tied up in the semantics of a question like this, such as by trying to define what is logical, believable, and finding an intersection between them. I think an easier approach is simply to take the title of the collection, "Just So Stories" at more than just face value. In many places, Kipling is taking a parental tone, giving the characters believable yet anachronistic or anthropomorphic qualities, but ultimately many of the justifications come down to "because I said so".
We should consider that Kipling did not, by any means, intend for these stories to be literally believable. So, perhaps rather than identifying what makes the story believable, we should look at elements of credibility. For example, when evaluating the truth of a statement, we often look at how it compares to our own experiences. Things which match our expectations are often accepted, things which do not are rejected, and things which come close are regarded with caution and skepticism. In the case of this story, it is immediately apparent that there are things we cannot accept, such as the animals all being the same color, or speaking. For someone more literal-minded, they might be unable to proceed past this point (I've occasionally heard children complain that a story like this can't be acceptable because it's full of lies). Instead, Kipling has set us up with the precept that this is not a believable story, and then he continuously injects elements that do match our expectations, which brings the story back toward being believable again. This is aided by the fact that Kipling doesn't take an overly zealous tone; it's a "yes, the animals speak, why do you ask?" sort of thing.
The story is a blend of credible and incredible ideas. Kipling carefully avoids drawing attention to or explaining these discrepancies. For example, he mentions that the Leopard and Ethiopian had nothing to eat for their tea-time; he completely ignores the fact that leopards don't drink tea, and instead treats this as characterization element that makes the leopard more sympathetic (as what child would want their tea-time spoiled for lack of anything to eat). It also makes the Leopard appear civilized and rational, even aside from his ability to speak.
The effect is to reverse our expectations; since Kipling explains very little, it is actually easier for us to just accept that a character, which in all other mannerisms is human, is actually a leopard. Put another way, if Kipling had chosen to explain all of these things, those explanations would distract us even further from a believable story.
The plot itself is also fairly credible; it is the transitions between the plot points that are incredible.
- The other animals are hunted
- The animals escape to a new habitat
- Leopard and the Ethiopian follow them
- They find the animals have adapted
- They adapt as well
This isn't really that much of a stretch, and it's probably what did happen both in terms of human civilization and evolution. It surely happens in our lives as well.
Another credible element is the way in which credible things are cross-utilized in incredible ways. For example, the leopard gets his spots via the Ethiopian basically finger-painting him black. Many people can probably clearly visualize the shape and appearance of the spots that would result, even if we know that finger-painting in this way wouldn't reasonably be able to change an animal's skin.