Oh--steam warships mainly needed to wait for the propellor. Side wheels are very vulnerable. Could the screw propeller show up a bit earlier? It wouldn't be much earlier; it's useless without a source of power.
Side wheels powered by animals or humans have been in existence a very long time. Perhaps someone thinks of the screw rather than the wheel. The former is more efficient, whatever power source used.
I'd second this, but "neolithic" might be a little early. There are those who speculate the the Nasca culture in South America may have had manned hot-air balloons to see their large markings from the air, but geometry is probably easier, huh?
Seriously, though, it is amazing that nobody thought to play around with the fact that hot air from a fire causes ash and other objects to rise. It is surprising that this innovation did not come much earlier - even if it was used only for displays and other events - somewhat like fireworks.
But it would take many major industrial innovations to turn this into a reliable flying machine
Hot air balloons did exist in China as an illumination tool. But apparently no one thought to put a man in it.
As far as flying is concerned, what about paragliders? Very simple, and at the same time a very recent invention.