Role/importance of letters of recommendation for PhD-applications in Europe?
We can distinguish two different kinds of doctoral graduate studies in Europe:


Programs through "graduate colleges" and "graduate schools" with centralized admissions policies
Individual PhD positions in the research group (or institute, chair, etc.) of an individual professor


In the first case, everything is essentially along the lines of an application to a US-based graduate program, and letters of recommendation still carry the same weight.

For an individual position, letters of reference may be important, but as you suggested, it depends on the individual professor doing the hiring. For some research groups, the posting of an application is a formality, as they're only interested in hiring "internal" candidates (that is, people who have already worked in the group as bachelor's or master's students, and who thus can be "directly" evaluated). For people doing real searches, however, letters of recommendation are also important, because they can provide information about a candidate's research abilities in a way that is not possible just looking at a transcript or set of certificates.