It's maybe useful to remember that a pigment doesn't become a paint until it's bound with something to hold the pigment particles together. One of the most common binders used worldwide was/is glue obtained from various animal sources. In the Far East naturally occurring minerals like red and yellow ochre, malachite, azurite and soot have been used for thousands of years. With the exception of soot, minerals were/are ground down and then bound together with a glue to form a paint. The glue used to bind traditional pigments in the Far East is still obtained from deer horn. Interestingly, the finer the mineral is ground the lighter in colour it becomes, so a coarsely ground piece of malachite will have a sandy texture and the colour of an oak leaf, while the same piece of malachite ground to a fine powder will be a very pale green.
Perhaps the very first paint was made from animal fats dripping onto a sooty surface - the kind of thing that might happen naturally around a campfire. Ink sticks in the Far East are basically still made by mixing soot (of various grades) with animal glue and then leaving the stick to harden. When the liquid ink is required the stick is ground on a stone with a little water. These kind of inorganic paints are pretty stable but the organic glue binding them can break down in quite a short period (10-20 years perhaps even in good conditions) returning those paints once again to powdery pigments where they might be easily washed, blown away or eroded by some other means.
What's slightly puzzling is that you'd expect some evidence (in the nooks and crannies of stones that have been buried for example) of paint if it had ever been used to enhance megaliths. It could simply be, though, that no-one has actually bothered to look and record trace remains of such paints on megaliths - an interesting research project for somebody perhaps :-)
