How did the same perfect-tense structure become so widespread in Europe?

The issue of the analytic perfect has been studied in the context of grammaticalization but I'm not sure that any one explanation for the spread of the construction has been agreed (perhaps somebody who knows the literature can elaborate). Most likely, different processes led to the emergence of the construction in different contexts.

The analytic perfect is also the feature of the Balkan Sprachbund meaning you can find it in Albanian and Greek as well as Romanian (Romance) and Macedonian (Slavic). This lends credence to the sprachbund explanation. The construction spread through areal contact and borrowing rather than through historical descent (although historical descent will have played a role in some cases).

But it would still be interesting to speculate as to the mechanism of the spread. Generally people talk about direct borrowing or imperfect learning as the main contact change mechanisms. Direct borrowing is a much harder case to be made with syntactic constructions but when one looks at the languages involved, it would be hard to construct a scenario where imperfect learning could account for the change.

Another possibility is simply parallel independent development. One of the features proposed as common to SAE (Standard Average European) was an analytic passive with a copula and a participle. It seems plausible that many languages could develop this type of perfect construction drawing on this features. Perhaps reinforced rather than directly introduced through contact.

It is also important to note that SAE tense and aspect systems are quite complex both diachronically and synchronically so looking at one form in isolation may not be the right approach.