I'm going to argue that the cultural aspects don't matter.
Well they matter some. Books (or written pages) and literacy need to exist. But we're talking about a king here. If he decides to humor the funny man from the future, he doesn't need a reason (and whether or not he does so is a story problem, not a Worldbuilding problem). He just needs the funds, workpower, materials, and underlying technology.
Let's assume that the king has available to him sufficient funds and skilled workers of all kinds. That's a pretty reasonable assumption for any kingdom not in crisis.
So what materials and tech do we need and when in European history did they exist?
Paper
While you can have books made out of vellum (animal skin), a printing press works on paper. Vellum (or a less fine parchment) I suppose is possible (especially for a rich kingdom) but paper really is the way to go.
Paper made out of plant like fibres was invented by the Chinese Cai
Lun, who in 105 AD mixed textile fibres and fibres from the bark of
the mulberry in water and produced sheets of paper from that. The
invention of paper was one of the reasons of the successes of early
China, through easier governing of the country. Archeological findings
have shown that paper made from plantlike fibres, were already used
from 140 to 87 BC. (ref)
That doesn't help us though. The question is specific to Europe and Europe and China weren't trading at that point.
The art of papermaking was first exported from China to Korea and
Japan around 610 AD. Arabic people have learned the papermaking
technique in the 8th century from Chinese, as is being told, from
Chinese people skilled in papermaking who were captured. The Arabic
people spread the knowledge during their military campaigns in the
North of Africa and the South of Europe. The first paper manufacturing
in Europe started in 1144 in Xativa (near Valencia) in Spain. The
first papermaking in countries in Europe, which were not controlled by
the Arabians, was in the 13th century in Italy and Spain, although the
usage of paper was already known in Europe since about 1100. A paper
mill in Fabriano (near Ascona) in Italy existed in 1276 (and still
exists nowadays). Around this time sizing paper with animal glue was
invented in Italy. The Germans had their first paper mill in 1389,
followed by the rest of Europe at the end of the 15th century. In
Belgium the first paper production was in Huy (Hoei) in 1405 and in
Holland in in Dordrecht in 1586.
So now it depends on where in Europe you are. If you're in a location with a paper mill, then it's easy. If you're somewhere that has regular trade with a paper mill location, that's also fine. Certainly trade routes were well established by the early Medieval era, but there were other trade routes as early as the 16th century BCE.
So let's assume that the king could acquire enough paper for these needs by the 12th century (paper mill in Spain) and maybe a bit earlier since he'll know to ask for it. Can the kingdom manufacture paper? Maybe. It's a bit more complicated than it seems so someone who doesn't know how might not be of much help. But with some trial and error, it's doable. Certainly by the start of the Roman era and probably sooner.
Ink
This one is easier.
The first man-made ink appeared in Egypt about 4,500 years ago and was
made from animal or vegetable charcoal (lampblack) mixed with glue.
(ref)
Ancient Rome had ink, Medieval Europe had ink (starting about 800 CE). So getting or even inventing a basic ink is pretty straightforward. Except...
In the 15th century, a new type of ink had to be developed in Europe
for the printing press by Johannes Gutenberg...Gutenberg's dye was
indelible, oil-based, and made from the soot of lamps (lamp-black)
mixed with varnish and egg white. Two types of ink were prevalent
at the time: the Greek and Roman writing ink (soot, glue, and water)
and the 12th century variety composed of ferrous sulfate, gall, gum,
and water. Neither of these handwriting inks could adhere to
printing surfaces without creating blurs. Eventually an oily,
varnish-like ink made of soot, turpentine, and walnut oil was created
specifically for the printing press. (ref)
This makes the printing task much harder. Our time traveler probably hasn't a clue about different kinds of ink, let alone how to make them. Maybe trial and error from skilled chemists, alchemists, or other material science types of workers, will do the trick. Maybe not. The ingredients aren't hard to find; the problem is the recipe.
Does this kill our timeline? Perhaps not. The question is about creating a printing press. Not successfully using one.
Fine metalworking
We need tiny type (they can be "large print" but that's still pretty small) made perfectly square. The upraised letters themselves have to be perfectly smooth and flat, with the rest of the metal type so uniform that they all fit together just so. And so they can be held fast with a frame such that none of them slip.
Around 1450, Johannes Gutenberg introduced the metal movable-type
printing press in Europe, along with innovations in casting the type
based on a matrix and hand mould. The small number of alphabetic
characters needed for European languages was an important factor.6
Gutenberg was the first to create his type pieces from an alloy of
lead, tin, and antimony—and these materials remained standard for 550
years. (ref)
The first moveable type printer (porcelain) comes from China in 1040 CE. The first metal one is from Korea in 1377. So this technology is not very old. Even wooden moveable type is from China in 1040. It just doesn't go back that far.
Stone molds for metalworking were around as early as 3000 BCE. And better casting arrived in Egypt not long after. Ancient Egyptians were making metal wire, including ones fine enough to weave into cloth, in the second millennium BCE, along with many other advanced techniques, including alloys that would work for printing.
The first iron working in Europe though was Ancient Greece in the late 10th century BCE. It took until the 8th century BCE to bring ironworking to Central Europe. And until 500 BCE for it to become common in Northern Europe, including Britain.
While bronze working began in Europe in the early 3000's BCE, it took a thousand years or more to spread outside of the Mediterranean. Mostly it was used for weapons and tools and not for very fine work like would be needed for type.
I think this is your sticking point. Yes, there was some fine metalworking available in Ancient times, even many centuries before the common era. But it was not consistent in the way we need.
To get type before the Medieval era or so, the king would have to send someone to an area that could make the type, who would stay for the months necessary to oversee the project.
The machine itself
Eh. This is the easy part. Wood, some basic metal. It's a press. Presses are old hat. It just has to be made very carefully so it fits together just so.
A perfectly flat surface with grooves or markings for the paper to fit. A hand roller to apply ink to the type after it's been fitted into the frame and attached to the machine.
A press mechanism to bring the type frame down on the paper. Done.
Conclusion
I'm going to put this about 1000 years before the common era.
The metalwork is the hardest part. It will likely be outsourced to Greece. But a set of several hundred letters, blanks, numbers, punctuation, etc, should last for many years. So who cares if it takes 2 years to acquire?
In that time, they'll get a source of paper and find an ink recipe that doesn't smear. Building the frame should take a few months and can't really be completed until the type arrives, since it must fit exactly.
Maybe a total of 3 years after the king says "sure, why the hell not?"