The "fixed stars" are not actually fixed, the earth's tilt changes over time etc., but all that happens slowly on human timescales.
Imagine a Babylonian astronomer (or astrologist?) teleported to the present, e.g. to present-day Iraq. Would she be able to tell that the sky is different? If so, what about a Maya astronomer? In other words, how long does it take until the changes in the sky are perceptible to the human eye?
Here's part of the sky in the year 1
It is part of the sky you may know well, Orion and the dogs. I've marked the current positions of Sirius, Procyon and Betelgeuse, with green markers so you can see how their positions have changed over 2000 years. It's not a lot.
The first thing that the Babylonian astronomer might notice is that there is a pole star, one that is fixed. 2000 years ago, Polaris was more than 10 degrees from the True North. Now it is less than 1 degree. It isn't immediately obvious from a casual glance at the sky, but it would be noticeable and surprising to Babylonian astronomer.
If they started looking at the position of stars at a particular time and a particular date, they would find that things are in the "wrong" position. Of course "on a particular date" assumes a calendar, and the Babylonian calendar was not the Gregorian calendar. With more measurement they would find that the point of Aries is now in Pisces. Again, its not something you would notice at a glance, but it is within the ability of a Babylonian astronomer.
Now the stars have actually moved since year 1. But it would not be casually noticeable. It would be within the ability of our Babylonian astronomer to measure, if we asked them to. The relative positions of Sirius and Betelgeuse have changed. The Babylonians could measure angles in the sky precisely enough. But we don't know if they did, and if they did we don't know if they wrote them down.
So our Babylonian would not look up and immediately say "something's wrong". But if we 1. Prepared him by telling them to take careful measurements of Polaris, Sirius and so on. and 2. Gave them some prompts on what to look for in terms of proper motion and precession, then it would be possible for them to observe some changes.
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)
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.
