I have a staircase not unlike your own, but timber not stone, currently fully carpeted. I want to paint the edges and have a stair runner, but a bit of research suggests a 66-year-old DIYer, experienced but doing it for the first time, is unlikely to produce good results. This is not least because of the turns; a straight run might be a starter. So a pro job and £££ - probably many more of them down here in that London than where you are! So far so irrelevant, but if you do end up painting the whole thing, you might consider Rust-Oleum floor paint. It's billed as for wood and concrete (= stone?). I've just done some new softwood floorboarding for a landing with it (matt, chalk white) and it's looking good, though not laid and walked on yet. I chose the paint because it's water-based rather than using polyurethane; I'm sure the latter will be tougher but I couldn't stand the fumes. Sand lightly and use knotting solution as per instructions, then - in my case at least - three coats. Let us know how you get on.