I wonder whether the birds or other flying animals heavier than air could evolve without trees of other protruding objects?
Trees were not involved with the evolution of flight in birds.
Birds did not evolve flight from gliders but likely from ground running predatory jumpers, birds and maniraptoran dinosaurs are about the most poorly designed climbers you could imagine there is zero support for tree climbing in early birds or their ancestors. So yes bird flight can and did evolve without the use of trees.
I should note birds are the only group of flying vertebrate this is true for, pterosaurs and bats did evolve from climbers.
These numbers are approximate, but our understanding of geology and palaeontology should mean these are accurate enough. Insects seem to predate trees by 15 million years. That is a lot of time - about the same distance in time between now and the release of the last book in the Game of Throne series!
To be honest, though... About 430 million years ago there were fungi whose fruiting bodies could reach up to 8m in height. They could have served the same role as trees for insects. And they predate insects by about 30 million years, or about the timespan between the roman empire and the release of Half Life 3.
The most accurate answer to a question like this is always going to be “We don’t know.” Evolution is an incredibly complex and fundamentally random process so there are no definitive answers here. But, that said, I think there’s good reason to believe flight probably would have evolved even without trees or other protrusions.
Flight is thought to have evolved 4 separate times on Earth. In insects, pterosaurs, bats, and birds. This suggests that flight isn’t extraordinarily difficult to evolve and serves as a useful adaptation in a variety of environments for a variety of organisms.
While trees certainly play a large part in the lives of plenty of birds, many birds thrive in treeless environments. Waterfowl like ducks spend their time swimming and generally build their nests on the ground. Seabirds like cormorants spend their lives fishing and often nest in colonies on the ground. There are also ground birds such as quails that nest and feed on the ground often in treeless areas. In all of these cases, some of the birds in these habitats have lost their ability to fly which implies that in the absence of trees flight isn't perhaps as critical to their survival. But most of these bird species living in treeless environments have retained their ability to fly which implies that it remains a useful ability for these organisms to find food, escape predators, or migrate.
Birds certainly tend to take advantage of trees when they are available but their success in treeless environments tells us that the safety of trees is not the only advantage of flight and suggests that there is ample reason for flight to evolve even in the absence of trees.
While I agree with the existing answers, what it comes down to is the question of what benefit does a creature get that makes the adaptation of flight worth it?
There are two basic benefits that I can see that a flying animal may have over a land based animal; protection and ambush.
The first is obvious; if you can take flight, you can scan a larger area for threats, but also you can escape those threats if you're on the ground via a vector your attacker probably can't follow. As for the second, well if there aren't a lot of other fliers out there yet, perhaps your prey doesn't know to look up from time to time and won't see you coming.
Of course, this makes the most sense if the energy tradeoff is small, therefore it follows that the first flying creatures would be as small as is practicable, taking advantage of the square cube law. It's little wonder therefore that the first flying creatures were small insects.
Since plants need light, and the tallest plant gets the best light, then if there were no trees there would inevitably be very tall plants that aren’t technically trees. However, they would function much like trees for ecological purposes, and animals would still climb them, jump between them and fall off them, so the evolution of flying animals of any kind would be unchanged. If you’re going to arbitrarily change the way evolution works to rule out tall plants, then you can equally arbitrarily rule birds in our out, depending on what you want — you’ve already given up on evolutionary plausibility.