There are a few fictional documentaries describing possible evolutionary traits in non-terrestrial animals (
Alien Planet,
Natural History of an Alien)...
With aliens, the question changes from "Can evolution get from A to B?" to "Can evolution get to B at all from anywhere?", so the answer is usually bound to be yes as long as the end point doesn't violate a law of physics, chemistry, geometry, or such.
In Wikipedia's list of organisms in NHoaA, the only one that stands out to me as having a basic physics/geometry problem is the "pagoda tree" (which I've seen somewhere before). They said the relatively small number of very large disks-shaped leaves are supposed to increase the surface area for absorbing sunlight and gas, but it would actually do the opposite. A large number of tiny structures will yield many times as much surface area in the same amount of space, which is why Earthling trees' leaves are the way they are, as well as the insides of our own intestines and lungs.
On "Alien Planet", giving a planet "low gravity and a thick atmosphere" is a common meme in science fiction (such as "Avatar") to make it plausible to have more cool fun stuff: more flying/floating/gliding, bigger sizes, and funkier less compact shapes with more spindly bits sticking out. As a justification, it generally works OK, but one flying critter took that theme too far with its methane-fuelled organic jet/rocket engines. That type of engine is great at hundreds of miles per hour, but at a much lower speed like what was shown, it's exremely inefficient with fuel/energy, and a thicker atmosphere (which helps some flight modes by generating more lift but also generates more drag) would only make it worse, and the animal's body didn't include much storage space for fuel. So the jet trick, even granting that it's possible at all, couldn't be used for more than short occasional bursts, like a lot of other animals' fast-but-inefficient top speed modes. But they were shown cruising arond that way all of the time.
On the ground, the predilection for bipeds and the fact that at least one of them apparently was blind don't defy physics, but are peculiar enough to look like the creators were just thinking "weird and different" more than "realistic and likely". One of the bipeds has a front foot and a back foot, and is shown galloping. Without separate right & left legs in front and back, it would need wide feet for left-right control, but they didn't make its feet wide. About the amoeba sea and sea strider, too little detail is given to say they're physically plausible or implausible. I liked the use of sonar, which becomes more practical & likely the thicker the air is. Sometimes the sounds even sounded a bit like underwater sounds, which was good because thicker air would act more like water, whether or not that's what the sound designers were thinking when they came up with those sounds.
...and one specific documentary on possible evolutionary directions in the far Earth future (
The Future is Wild).
I didn't see it, but, going by Wikipedia's critter list and searching for images of them by name...
At 5 million years: mostly just minor adjustments to present animals, which make sense and don't bump into any particular reasons why they couldn't happen. A small-jawed, small-toothed predator turning saber-toothed makes me wonder, because other saber-toothed animals have only existed in environments where the herbivorous prey were huge, but I can't say it's just wrong.
They did get pretty weird about the birds, though. The amount of change from caracara to "carakiller" is enormous for just 5 million years, including one part (reversion of wings to dinosaur arms) that's unprecedented. I don't get how they picked which present bird to say this happened to, since the end result has practically no connection to the starting point. And there are intermediate stages they'd need to rush through along the way that are similar to real birds that have stayed roughly the same for several times that long, such as turkeys. Then they have two other bird species ending up in specialized forms based on quadrupedal or duadruped-derived real-life models, implying that those birds, with no quadrupedal ancestors since before the dinosaurs, became quadrupeds again along the way just so they could then switch to imitating moles or seals, which also requires changing the specialization of the front limbs in at least one case and getting the back to move in ways no saurischian's back has ever moved in the other case.
I guess the reason they got carried away with the birds, and borrowed from mammals to do it, was because birds haven't yet taken on as much variety of forms as mammals have. Unfortunately for that line of thinking, there's a reason for that. In general, once something is specialized, de-specialization or a change in specialization doesn't happen, at least not in only about as much time as we have been separate from chimpanzees. It's not just that we're talking about changing birds to a form based on certain kinds of mammals; suggesting bats evolving into something like moles or seals, especially so fast, would create just about the same problems.
At 100 million years: This is plenty of time for large-scale changes. For example, most major groups of mammals separated & differentiated from each other less than this long ago. So I generally won't complain about changes being too drastic for the time allowed.
Most of the suggested organisms are described taking paths that some real ones have before, so they're known to be possible. Sometimes there's just an issue of what steps would be needed to get there. The biggest one is coming out of the water onto land, which is a neat trick for an octopus. But they did at least think about what the challenges were and address them. It's still crawling around in swamps and its overall shape looks like it probably still swims too, so it might not need any other way to avoid dehydration yet. I can see that four of its arms are modified for minimal support & locomotion on land. The big thing that leaves is breathing air, and the pictures I see have a couple of extra holes that present octopuses don't have, so I'll figure those are for the respiratory system. Where a respiratory system came from, I don't know, but it doesn't really matter as long as the creators thought to put something there. (Real animals evolving from aquatic to terrestrial have handled respiration at least three different ways.)
If a tortoise stands up on vertical legs and is much bigger than an elephant, why does it still have a shell over its shoulders & hips? (Not an problem, not wrong, just makes me wonder why)
Why are poggles the last land mammals (and relegated to caves)? Mammals aren't going extinct without something specific causing it. Is the global temperature supposed to be to high for the rest?
At 200 million years: I don't understand flish. Pictures of one of the two species look like birds, and pictures of the other look like fish (with funky extending jaws). If they're supposed to be derived straight from "flying fish" without walking first, then not only did their fins need some work to be able to flap, but there's a huge energy utilization gap for them to have bridged. I believe flying fish don't have lungs, but even if they do/did, a lungfish "lung" is just a bag of air, and birds' lungs are much more complex and have higher gas exchange capacity than even mammals'. What drove the improvements before these critters began flying? Also, the described activity level for at least one of the two species means it must be warm-blooded, but fish aren't, because of water's low oxygen content and high heat transfer rate compared to air, so when & how did this one get warm-blooded? I won't say there isn't any evolutionary path to get to an animal like what they had in mind, but I will say it can't really be called a "fish" anymore, any more than real tetrapods are fish now, and calling it that is obscuring what the possible paths might have been.
Is physical support for lichen trees addressed? Normal trees deposit wood inside themselves, made from a protein and a polysaccharide. But how they do that is related to the fact that they're vascular (they have vessels), which lichens are not. I guess we're just supposed to infer that they must have evolved a way to produce something like wood, and probably had to become vascular first, which would have made them not really what people think of when they see the word "lichens" anymore.
If slithersuckers have as much structure and structural integrity to them as those ribbony hanging things in the pictures, then they're not slime molds anymore, even if they did descend from one. Slime molds are just fungi whose intercellular matrix material allows the cells to move past each other a lot; solid molds and other fungi have substances connecting the cells to each other more solidly. To convert one to the other, just change the recipe of the intercellular stuff. But these are also said to be carnivorous; how do they kill?
Squibbons... didn't "tree squid" originate as a joke? I can't tell which structures in the pictures are what, or how big they are, so all I can say is that if those things came from squid, then they're full of modifications making them not much like squid anymore, which is fine because they'd need to be. We could make a list of specific changes they might need along the way, but the show's creators have given no reason to think that it couldn't have happened in this case.
But I'm not buying the megasquid. One of the images you can find of it explains how its legs, which have gotten thick, straight, stumpy, and vertical, hold up its tons of weight using a pattern of muscles aligned perpendicular to each other, instead of a hard skeleton. I'm not aware of any precedent for that, but even if it can work, it doesn't keep the internal organs together on top of the legs, so where's the support for the guts? Worse yet, the same diagram says air gets into the lung
through the mantle. You can't use diffusion at that size; you need a macrosopic, specialized system of organs using macroscopic holes on the outside. Why did they follow that with the swampus but not here?