How much does the sky change in a few thousand years?

Some stars change their positions significantly, and certainly measurably to the naked eye on timescales of a few thousand years (if you were to look carefully). It depends on their relative motion perpendicular to our line of sight and their distance from us. Nearby stars are more likely to show larger motions, because a given tangential velocity difference translates into a bigger angular speed on the sky.

This video from the ESA Gaia mission simulates the next 450,000 years of the Orion constellation. Some stars, particularly Betelgeuse, would move enough in about 5000 years to be in noticeably different places to where they are now.

The biggest systematic change is caused by the precession of the earth's orbit, with a period of about 26,000 years.

To observe and deduce anything about that relies on record keeping. There is no hard evidence that the ancient Babylonian or Egyptian astronomers kept any relevant long term records.

The earliest known discovery of this phenomenon is attributed to the ancient Greek astronomers. Hipparchus (c.150 BC) used observations made by his predecessors 250 years earlier, noted changes of about 2 degrees in the position of "fixed" stars, and proposed an explanation using a model of something similar to precession with a maximum period of 36,000 years. Not all of his contemporary astronomers accepted this idea, however.

We don't have a first-hand account of what Hipparchus did since all his known writings have been lost, but his theory was described by Ptolemy about 100 years later. It is not clear whether Ptolemy made independent observations to confirm Hipparchus' results, or merely extrapolated them by 100 years to his own time.

The time interval between the ancient astromomers and the present represents about 10% of the precession period, so if an ancient astronomer was teleported 2,500 years to the present day it seems quite likely they would notice "something had changed." For example the Egyptians based their calendar on the heliacal rising of various stars, and it seems plausible they would notice that their calendar was now about a month out of sync with the seasons they were familiar with - in particular, the date of the annual Nile floods. (That statement ignores the effect of the modern Nile dams on the river's behavior, of course!)

It depends on many factors, primarly how you define "perceptible to the human eye". The parameter measuring the movement of the stars is called proper motion, and it depends mainly on the dynamics of the star and the distance. Each star has it own proper motion, so it's difficult to give a general answer to your question. There are several examples of changes in the shape of constellations due to this effect (here is an animation for the Big Dipper)