Short Answer:
In my opinion the best method would be for the aliens to leave a sky map showing an unique arrangement of planets in the sky at the time of the predicted event.
Long Answer:
You didn't say that the aliens visited Earth 4,999 years before your story and said that 5,001 years later, or 2 years after your story opens, the pattern would be visible in Earth's sky.
You didn't say that the aliens visited Earth in AD 2024 and said that 4,999 years later, or AD 7023, when your story opens, the pattern would be visible in Earth's sky.
And you didn't say when or even if the dates of the aliens' visit and of the future pattern in the sky were between those extremes.
Part One: Changing Constellations.
You will want to consider the apparent change of position of stars as seen from Earth. If the distance to a star is known reasonably accurately, astronomers need two pieces of data to chart its past or future apparent position as seen from Earth.
They need its radial velocity toward or away from Earth, found by measuring the red or blue shift its spectrum. And they need its proper motion, the angle that it appears to move sideways in the sky each year, found by periodically measuring its position in the sky.
And today there are a lot of relatively accurate measurements of the distances to stars and their radial velocities and proper motions.
here is a link to a list of nearest stars and brown dwarfs:
https://en.wikipedia.org/wiki/List_of_nearest_stars_and_brown_dwarfs
Here is a link to a list of the brightest stars as seen from Earth:
https://en.wikipedia.org/wiki/List_of_brightest_stars
It lists the 92 stars which appear brightest as seen from Earth. There are a few thousand other naked eye stars which appear less bright.
Here is a link to a list of a few stars which have the highest proper motion:
https://en.wikipedia.org/wiki/Proper_motion#Stars_with_high_proper_motion
And what you need is to find one or more stars which are on all three lists. You probably will have to settle for stars which are on only two of those lists.
A naked eye visible star with exceptionally large proper motion might possibly noticeably change the shape of any asterism or constellation it is part of within a few thousand years.
Here is a link to an article which mentions some computer programs which display changes in constellations over time.
https://opticsmag.com/do-constellations-move-and-change-over-time/
Here is a link to an article about changes in the constellation Orion over 450,000 years. I doubt that there would be noticeable changes in only 5,000 years.
https://www.space.com/37148-orion-constellation-changes-over-450000-years.html
Part Two: Precession of the Axis.
"Slumber, watcher, till the spheres,
Six and twenty thousand years
Have revolv'd, and I return..."
H. P. Loevecraft "Polaris"
The Earth turns around its axis of rotation, an imaginary line between the north and south poles extending infinitely into outer space. Due to the precession of the axis it slowly wobbles in a circle a period of about 26,000 years.
A consequence of the precession is a changing pole star. Currently Polaris is extremely well suited to mark the position of the north celestial pole, as Polaris is a moderately bright star with a visual magnitude of 2.1 (variable), and it is located about one degree from the pole, with no stars of similar brightness too close.6
The previous pole star was Kochab (Beta Ursae Minoris, β UMi, β Ursae Minoris), the brightest star in the bowl of the "Little Dipper", located 16 degrees from Polaris. It held that role from 1500 BC to AD 500.7 It was not quite as accurate in its day as Polaris is today.7 Today, Kochab and its neighbor Pherkad are referred to as the "Guardians of the Pole" (meaning Polaris).7
On the other hand, Thuban in the constellation Draco, which was the pole star in 3000 BC, is much less conspicuous at magnitude 3.67 (one-fifth as bright as Polaris); today it is invisible in light-polluted urban skies.
https://en.wikipedia.org/wiki/Axial_precession#Changing_pole_stars
Here us a link to a star chart showing the path of the north celestial pole over a full cycle of 26,000 years.
https://en.wikipedia.org/wiki/Axial_precession#/media/File:Precession_N.gif
To be continued:
Continued Nov. 15, 2023:
Looking at this star chart of the precession of the axis:
https://en.wikipedia.org/wiki/Axial_precession#/media/File:Precession_N.gif
You will see that Alpha Lyrae, Vega, the fifth brightest star as seen from Earth, will be the pole star about 12,000 years in the future or about AD 14000, and was the pole star about 14,000 years ago or 12000 BC.
At present the pole star is Polaris, but around 12,000 BCE the pole was pointed only five degrees away from Vega. Through precession, the pole will again pass near Vega around 14,000 CE.[33] Vega is the brightest of the successive northern pole stars.10
https://en.wikipedia.org/wiki/Vega#Observation
Alpha Cygni, Deneb, will be the pole star about 8,000 years from now, about AD 10000, and was the pole star about 16,000 years ago, about 14000 BC.
Due to the Earth's axial precession, Deneb will be an approximate pole star (7° off of the north celestial pole) at around 9800 AD.12 The north pole of Mars points to the midpoint of the line connecting Deneb and the star Alderamin.20
https://en.wikipedia.org/wiki/Deneb
Part Three: Double Stars.
To be continued:
Continued 11-15-2023.
For people on Earth to see that the positions of the two stars in a double star have changed, both stars have to be bright enough to be seen from Earth at their distance, and the separation separation between the two stars has to be great enough that they appear as two separate stars instead of one single star as seen from Earth.
If the line of sight from Earth to the star system is on the plane of the orbit of the two stars around their common center of gravity people might not notice the difference after 5,000 years. If star A was at the right of Star B 5,000 years ago and now is at the left of Star B, people might just see two stars side by like like they were 5,000 years ago and not see any difference.
But if the line from Earth to the stars is at an angle to the plane in which the two stars orbit, they will seem to move around their center of gravity, or maybe one will seem to circle the other one. The best angle would be if the line of sight was perpendicular to the plane in which the stars orbit each other. That would make their motions appear to be the most curved.
You asked:
Question: Can stars form binary and/or trinary combinations with enough separation between the stars to rationalize an observed movement of up to 20° in Earth's9 night sky over a period of 5,000 years?
There are two possible interpretations of that that question.
One interpretation is that the question asks where the coordinates of a star in the sky as seen from Earth can change by up to 20 degrees of arc over a period of 5,000 years.
Barnard's (Runaway) Star has the largest proper motion (change of angle as seen from Earth) of any known star.
The 10.3 arcseconds it travels in a year amount to a quarter of a degree in a human lifetime, roughly half the angular diameter of the full Moon.14
https://en.wikipedia.org/wiki/Barnard%27s_Star#Description
In 5,000 years the angular position of Barnard's star should change by about 51,500 arc seconds or 858.3333 arc minutes or 14.30555 degrees of arc.
But, even though Barnard's Star is the second closest star system to Earth, it is so dim that it can't be seen with the unaided eye from Earth. Ancient people would be unable to see it 5,000 years ago, so if the aliens left a set of star charts on Earth, one for 5,000 years ago and one for today, the people of 5,000 ago would not see Barnard's star where it was supposed to be 5,000 years ago.
Of the 9 stars with the highest proper motion, only Groombridge 1830, 61 Cygni, and Epsilon Indi are visible to the unaided human eye from Earth, and they look quite dim and inconspicuous from Earth. And of course their positions would change by much less than 20 degrees in 5,000 years.
The other interpretation is that the angle between two stars, their position angle, would change by 20 degrees of arc in 5,000 years.
And that is quite possible in a binary system. If it took 5,000 years for the two orbiting stars to change position by 20 degrees of arc, they would take about 90,000 years to make a full orbit of each other, changing from an original position angle to one at right angles, to 180 degrees from the original position, to 270 degrees and back to the orig0nial position angle.
And of course the more widely the two members of the double star are as seen from Earth, the easier it will be for people to notice a change in their position angle.
The maximum angular resolution of the human eye is 28 arc seconds or 0.47 arc minutes,[22] this gives an angular resolution of 0.008 degrees, and at a distance of 1 km corresponds to 136 mm. This is equal to 0.94 arc minutes per line pair (one white and one black line), or 0.016 degrees. For a pixel pair (one white and one black pixel) this gives a pixel density of 128 pixels per degree (PPD).
https://en.wikipedia.org/wiki/Visual_acuity#%22Normal%22_visual_acuity
It is easy to see the phases of Venus in a telescope.
In the realm of naked eye astronomy it has always been considered one of the greatest challenges to view the crescent phase of Venus. It is said that those with the best vision can just barely accomplish this when Venus is at its thinnest crescent phase. At this point Venus has an angular diameter of very close to one arc minute.
https://www.cloudynights.com/articles/cat/articles/optical-theory/venus-phase-naked-eye-experiment-r1366
I have sometimes thought that I might be just barely seeing a crescent Venus.
So if some humans can sometimes see a crescent Venus they might be able to just barely separate two stars with half an arch minute between them. But it would be very rare and unusual.
Here is a link to an article about seeing naked eye double stars, where the two stars are both bright enough to be seen from Earth and are separated by a wide enough angle to be seen as two separate dots of light.
https://skyandtelescope.org/astronomy-news/observing-news/see-summers-best-naked-eye-double-stars-07092014/
Now let's take a look at the real deal. My selection criteria were simple: each member of the stellar pair had to be equal to or brighter than the 6th-magnitude naked-eye limit and separated by a minimum of 2 arcminutes. While the human eye can resolve details only 1′ across, most of us can do 2′ at best. I'm guessing you'll find that taxing enough.
So they claim that most people can only see two separate stars if they are separated by two arc minutes. And probably several times two arc minutes visual separation might be needed to be certain of the position angle. I think that a change of about 90 degrees in the position angle would be the most likely to be noticed, and for the position angle to change by 90 degrees in 5,000 years the orbital period would have to be about 20,000 years.
Stars mentioned are Mizar and Alcor, Alpha Librae or Zubenelgenubi, Epsilon 1 & 2 Lyrae, and Beta Capricornii. Apparently those are the only good naked eye double stars in the summer sky that are actual binary stars orbiting each other instead of widely separated stars which are lined up as seen from Earth.
Mizar and Alcor are moving together in space.
However, it has yet to be demonstrated conclusively that they are gravitationally bound.
If they are exactly the same distance from us then the distance between them is only 17800 AU (0.281 ly).5
https://en.wikipedia.org/wiki/Mizar_and_Alcor
Alpha Centauri C or Proxima Centauri orbits Alpha Centauri A & B at distances between about 4,300and 13,000 AU and has an orbital period of about 547,000 years. So even if Alcor and Mizar are gravitationally bound the orbital period would probably be longer than 90,000 years.
The two main components of Alpha Librae or Zubenelgenubi are separated by about 5,400 AU.
The two are separated by at least 5500 Astronomical Units, nearly 140 times Pluto's distance from the Sun, and maybe more since we do not know the exact difference in distance. At that separation, the orbital period would be over 200,000 years.
https://web.archive.org/web/20050818161632/http://www.astro.uiuc.edu/~kaler/sow/zubenel.html
Epsilon Lyrae, "the double double", is two binaries - each of which can be seen as a binary in telescopes. The two binaries form a quadruple system, orbiting each other at a vast distance, but from Earth the two binaries appear so close that it is very hard to see them as separate stars with the naked eye.
Remarkably, each pair is also physically connected to the other. Separated by 0.16 light years they would take hundreds of thousands of years to complete an orbit. The pairs themselves are separated by 208" in position angle 173o. Binoculars may show the widely separated pairs as two stars and some keen-eyed observers may be able to discern them with their eyes alone.
https://observing.skyhound.com/archives/jul/HR_7051.html
As for Beta Capricornii:
Beta1 Capricorni is the brighter of the two components with an apparent magnitude of +3.05, while the dimmer Beta2 Capricorni has an apparent magnitude of +6.09. The two components are separated by 3.5 arcminutes on the sky, putting them at least 21,000 AU (0.34 light-years) apart. They take approximately 700,000 years to complete one orbit.
https://en.wikipedia.org/wiki/Beta_Capricorni
Here is a link to another article about naked eye double stars:
https://www.astropix.com/html/observing/20_fun_naked_eye_doubles.html
Of the stars listed, Zeta Corvii and HR 4691 might be an actual binary instead of an optical double.
It is separated by 7 arcminutes from the star HR 4691. The two may be an optical double or a true multiple star system, with a separation of at least 50,000 astronomical units and the stars taking 3.5 million years to orbit each other.
https://en.wikipedia.org/wiki/Zeta_Corvi
He also lists Mizar and Alcor, Alpha Librae or Zubenelgenubi, and Epsilon Lyrae, discussed above.
So it seems unlikely that there are any naked eye binary stars with orbital periods as short as 90,000 years for a 20 degree change in position angle in 5,000 years. Let alone ones with orbital periods of 20,000 years and 45 degree changes in the position angle in 5,000 years.
[Added Nov. 18, 2023. I asked a question whether there are any binary stars where both stars can be seen separately from Earth without telescopes, and with orbital periods less than 100,000 years, and the answers so far aren't encouraging.
https://astronomy.stackexchange.com/questions/55301/are-there-naked-eye-binary-stars-with-periods-less-than-100-000-years]
Part Four: Planets.
Approximately one hemisphere of the sky is visible at night from Earth.
There are five planets visible to the naked eye and known to the ancients. At anyone moment between zero and all five of them may be visible in the night sky. If the moon is not bright, many stars will be visible in the night sky, and it will be easy to see the positions of the planets relative to various stars and constellations.
Saturn has an orbital period of about 29.4 years, so it will remain in front of a zodiac constellation for about 2.5 years, while Jupiter has anoribitalpeirod of about 11.9 years, and so remains in front of a zodiac constellation for about a year. Mars has an orbital period of about 1.9 years. Mercury and Venus are seen only in twilight when few stars are visible.
Of course the positions of planets were recorded, even by ancient naked eye observers, much more precisely than merely the constellations they were in.
So my recommendation is that you select a time for the predicted event, such as July 1, 2025, or January 1, 2030, etc., and then use a planetarium program to show what the night sky will look like at that time.
Then use that planetarium program to search for previous times when the planets were in the same position in the night sky. And I think is quite likely that the planetarium program won't be able to find a previous example in the last 5,000 years. For example, in June 2022, Mercury, Venus, Mars, Jupiter, and Saturn were all close together in the predawn sky. That won't be seen again until 2040. And it is a little disappointing for the purpose of my answer that there will be only 8 years between those planetary alignments.
But those planetary alignments may happen in front of different constellations each time, in a cycle which may last for many decades or centuries.
And when an alignment of the planets within the same constellation reoccurs, the planets might not be in exactly the same positions relative to each other and to specific stars. Repetitions of the same configuration may take several such alignment sin the same constellation.
And then there is the Moon - will it be visible, what phase will it have, what constellation will it be in.
And the aliens might have included objects which are only visible in telescopes in the sky map for the future event, believing that human should have telescopes by then. The planets Uranus and Neptune, for example, which should make the specific position of the planets much rarer. And they could include the positions of the Galilean moons of Jupiter and Titan, the largest moon of Saturn. I doubt whether any particular arrangement at any particular date of all 13 of those objects in the sky of Earth has ever been repeated in the 4.6 billions years the solar system existed.