First deal with steps 1, 2 and 3. Clear away the weeds, clean the milestone with a bucket of clean water and a scrubbing brush. You need to remove any old flaking paint, but if the old paint is sound, leave it. Leave the milestone to dry. Painting wet stonework is a waste of time, because the paint will just flake off again.
The original paint is likely to have been limewash, which provides a protective sacrificial coating, but does not work well on granite or gritstone and does not bond well with sandstone. Masonry paint sold at your DIY superstore is designed for painting stonework, e.g. Sandtex. Choose a smooth white finish. Buy the best quality you can afford. It will cover better and last longer than a cheaper brand. Masonry paint is water based, so cleaning up spillages will not involve using chemicals with potential to damage the environment.
Some milestones are made from quite soft stone and may require more specialist paint, so that the paint does not cause a top layer of stone to flake off. Ask the Highways people, ask a local stonemason or research local stone types on the internet…
Inset lettering will need to be picked out with a smaller brush. Black masonry paint or black enamel should be used for this.