Europe is rather a large and diverse place, and I wouldn't try to answer for the whole place.
I have not had any trouble finding decaf at restaurants in France, Benelux, and Italy. Additionally, Starbucks is starting to become a serious presence in western Europe (to say nothing of Asia), and decaf is very much available there.