Hcfyk

1. 
   

   The printing press is not what Gutenberg invented. The printing press itself was known in Europe since the High Middle Ages at least, and in China even earlier. He did not invent movable type, which was also known.

   
   
   

   As for the "mechanization skills" needed -- printing was the last of the basic industries to be mechanized. Printing remained extremely labor-intensive up to the very end of the 17th century, and not extremely but still very labor-intensive to the end of the 18th. In the 15th, 16th and most of the 17th century a printing press looked something like this:

   
   
   

   

   
   
   

   A printing shop in 1568. The press is on the right; note that it is a very crude press, with a vertical screw and huge manual winding handles. The man next to the press is applying ink to the printing form. The man next to him has just taken a freshly printed sheet off the form and is examining it and placing it on top of the previously printed sheets. Picture from the 16th century, available on Wikimedia.

   
   


2. 
   

   Looking at how a printing press really looked like for the first three centuries of the history of printing, one would have to ask what exactly was the contribution of a jeweller? Glad you asked, because what Gutenberg invented was much more important that the press itself (which was already in use) and the idea of movable type (which had come and gone many times).

   
   
   

   He invented the hand mould, a simple yet crafty device used for making typographic letters (which are called "sorts" in typographic language).

   
   
   

   You see, the basic issue with the idea of printing with movable type was that the printer had to make many many As, many many Bs (but only about 1/10 as many as As), many many Cs and so on. As long as each letter had to be made individually this was basically so labor-intensive as to be uneconomical.

   
   
   

   Gutenberg, a jeweller by trade, came up with the following idea:

   
   
   
   
   

   • Make one hard-steel letter punch or master letter of each sort: one uppercase A, one lowercase a, one B, one b and so on. Repeat for each type size you need. This is done by very highly skilled people, usually with jeweller training.

   
   

   • To make a batch of type (type was usually sold by weight, say 10 pounds of type, containing an empirically-determined mix of letters), use the hand mould. The hand mould is a rectangular steel tube, one end of which can be stopped with a replaceable mild steel block; take the master letter in hard steel, put it in the tube and give it a whack with a hammer: it will leave an exact negative impression on the mild steel stopper. This is called the matrix.

   
   

   • Once the matrix (negative impression) has been made, melt a suitable amount of printer's alloy (an alloy of lead, antimony and tin, also invented by Gutenberg) and pour it in the tube; you will get a copy of the letter. Repeat and repeat and repeat until you have the desired amount of letters. Each of the sorts produced by this process looks like this:

   
   
   
   

   

   
   
   

   Diagram of a cast metal sort. Public domain picture from Wikipedia.

   
   
   

   One may want to notice that this is a very very manual process. Printing in general remained a very very manual process up to the end of the 18th century, and was not truly automated until the end of the 19th. See the brief and not entirely misleading Wikipedia articles on movable type and the history of Western typography.

   
   


3. 
   

   The conclusion is that printing presses with movable type could be built any time since the end of the antiquity; all they really needed was:

   
   
   
   
   

   • Paper (because while printing on vellum is technically possible, and it is actually done for real, the cost of vellum would have been prohibitive);

   
   

   • Access to lead, antimony and tin (availble since the antiquity); and

   
   

   • Access to small amounts of hard steel (available for import from India through Damascus since the late antiquity).

   
   
   
   

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?"

Simple (but probably wrong) answer: about the same time as the Antikythera Mechanism.

Simple (but definitely unhelpful) answer: early to mid 1400s.

Long answer:

I'd argue that the printing press isn't the critical thing.

Moveable type dates back to 1800BCE on Crete, as demonstrated by the Phaestos Disk. Block printing existed in China before the 8th century CE, and screw-presses existed in Asia and Europe for a good hundred years before Gutenberg made his particular contribution.

It isn't clear when complex mechanical devcices could first be made, but the Antikythera Mechanism is a pretty fancy bit of gear, and appears somewhere aroud the first century BCE.

The problem is one of motivation. Your question shouldn't be "who could build a printing press" but rather "when would people be prepared to make printing presses to disseminate knowledge and educate the masses", because that's a whole other kettle of fish. Those ancient kings you're trying to pitch to? They'd probably wonder why on earth a peasant needed to know about mathematics and logic, cos it ain't gonna do much for their day to day lives.

I'd be looking at persuading the church, not the state. Christian monasteries had things like Scriptoria from ~500CE, where monks would copy books allowing knowledge to be (slightly) more reliably maintained and disseminated (even if it was largely for missionary purposes at the time). From my highly uneducated point of view, it looks like a monk named Cassiodorus popularised the idea of copying books, and his important work Institutiones which included discussion on the subject was finished around 550 or so. The poor schmucks who actually had to do the grunt work of copying would probably have killed for a mechanised way of doing so. The Carolingian Renaissance and formation of the Holy Roman Empire is probably when this sort of thing really took off, and that wasn't until the late 700s.

Secular (you could probably also describe them as "professional") scribe services appeared not long before Gutenberg's press (relatively speaking), and this isn't a coincidence. Also, around the same era, you get Medieval Universities. Again, not a coincidence.

The printing press facilitated a change, but the environment in which it appeared was already ripe for that change. Without that huge social and cultural foundation, it simply wouldn't have had the impact it did. This is a similar problem to all the other time-travel-technology questions; stuff never arose in a vacuum!