Annatto is a common spice in Mexican cookery, especially in the Yucatan. However, like many Mexican ingredients, it's hard to find in Europe. What can I use as a substitute to give the same colour and approximate flavour?
The flavor is described as being very mild and unless the recipe calls for a ton of the stuff it is probably being used mostly for color.
The color it gives is a yellow-orange. Substitutions used are turmeric, paprika, or a mixture of the two. It was often used itself as a substitution for saffron but of course saffron would be too expensive to make the substitution back.
If your recipe does use a lot of annatto (or you are serving it to people who claim to be able to detect the difference) then your best bet would probably be to just buy it online. It is a seed so it isn't fragile and ships well.
Annatto (or achiote) is occasionally used in Portugal and Spain and is commonly used in English cheeses like Gloucester and some cheddars, including French Mimolette; it wasn't that hard to find in Germany, in my experience, when I lived there, though I think I tended to buy it at small markets run by Turkish immigrants or other ethnic markets. So I would challenge your assertion that it's particularly hard to find in Europe; it's in plenty of foods and is a recognized additive (E160b).
In Mexico annatto is a common alternative to saffron, so you could go that route, though I imagine saffron is more expensive than even mail ordering annatto seeds. Turmeric offers the color, without the nice flavor of annatto cooked oils. (Fresh turmeric has a good flavor of its own, though).
There is no substitute here. You can use something else to give you a red/orange color, but annatto seed is the main ingredient and main flavor in achiote paste, so if you replace it, you aren't making achiote paste - you are making a different, possibly tasty paste. It would be the equivalent of saying "what can I use instead of tomatoes in tomato sauce?"