To some extent, it depends on what the stepping stones are made of - some cleaners are suitable for concrete paving slabs and not for natural stone. The stains will have been caused by the iron content in the fertilizer within the Evergreen product. This staining can be because you managed to get some on top of the slabs and didn't remove it immediately, but also occurs from the bottom up, that is, when the lawn is wet from rain or you watering it, the fertilizer starts to dissolve, and may penetrate the underside of the slabs as well as the top as a solution in the water. If you've had a lot of rain, its likely both top and bottom of the stones have been soaking up the solution.
You can try the following types of product, but the truth is, if the fertilizer in the product you used is a slow release type, that could take anything up to 4 months to degrade, which means the staining may actually get worse during that time, and any efforts you make to remove the stains might be best left until you know the fertilizer is no longer active. The first link is to a product for concrete paving which may or may not be suitable for natural stone
http://www.theruststore.com/How-Do-I-Remove-Rust-Stains-Caused-By-Fertilizer-W44.aspx
And this one is for natural stone paving: Lithofin BER1 BERO Rust Remover and Stone Cleaner, available at Amazon in the UK, not sure about anywhere else, link below
http://www.amazon.co.uk/Lithofin-BER1-Remover-Stone-Cleaner/dp/B000WXTVUU/ref=sr_1_1?ie=UTF8&qid=1439119220&sr=8-1&keywords=lithofin+bero
Regarding the tarmac, the staining might just disappear on its own, but I found this - its aimed at removing battery acid stains, but may well work to clean the tarmac - might also deal with the staining on the stones
http://www.front9restoration.com/products/f9b-a-r-c/
All these products must not be allowed to leach onto planted areas, including your lawn - they'll kill the grass, so you'd probably need to lift the stones and treat them, then replace.