Well, the first thing you need to do is get paper distributed more widely, and manufactured more cheaply.
While paper manufacture was apparently introduced to Sicily and Iberia by the Arabs ~1000, it took much longer to move north. So you probably want your printing press to be invented somewhere in e.g. Italy (maybe Norman Sicily).
Wiki says the first water powered papermill didn't happen until 1411 (I think it was), and papermills are surely critical for getting the price down enough to make printing viable.
Vellum/parchment, etc., are simply not going to work for your purposes. The cost of the animals used, and the processing, are too high to allow for significant publications.
---
So. Someone in Norman Sicily invents a printing press ca. 1100 or a bit later, using paper produced locally. The Duke uses the press for propaganda purposes (printing pamphlets proclaiming his position in conflicts with e.g. the Pope). At this point, paper is expensive enough, and the printing tech poor enough that it is just up to printing, say, 100 copies (at a time) of the Duke's 2 page document to be sent to every monastery and major noble in Italy. (OK, so that takes a couple of print runs of 100 each.)
The Pope realizes the PR advantages of this method, and encourages HIS monasteries to figure out how to reply. (OK, so the FIRST reaction is to call the procedure diabolical. Maybe the next Pope is the one who figures out he has to respond in kind.)
Once the Papacy has this minimal sort of printing press, they can use it to send identical documents to every Bishop in Europe.
Increasing use of such presses leads to a vastly increased demand for paper, and better methods to produce it. Similarly, better presses.
Slowly, printed documents (initially only a few pages) gradually become a tool of Papal and Royal power/reach.
By 1300 or so, the situation has gotten to the point of OTL's Gutenberg. That quality of type, that speed of use and that cheapness of paper.
OTOH, because the process is so gradual, the powers that be manage to co-opt it and manage it more successfully than OTL (the ability of pampheleteers to publish their own works of theology and/or polemics didn't suddenly spring on the scene for instance.)