Orbiter - Realistic orbit dynamics in our own solar system. The challenge here is to learn how to navigate, it's unbelievably rewarding!
Noctis - Old exploration game, it might be difficult getting it to work on newer machines (try Dosbox). It generates procedurally a whole galaxy, allowing you to go anywhere and even go for a walk on the surface (sounds like what you want to make!)
Kerbal Space Program - Still in Beta. So far it plays like a more casual orbiter, but in a fantasy system (so far it only has the main planet
So, yes, it is possible to have things in this scale. It's obviously more complex than simply using one metric system and huge float numbers, you'll need to break the space into sectors at the very least. Here's a nice article on the subject:
The author of this article works on a similar project, but I don't think it's still in development. Link.
I also am very interested in building a simulator like this! But what kills my motivation a little is that right now we don't have the technology to really build worlds that are interesting procedurally. Noctis is basically different frequencies for the perlin noise terrain and different colors. And this pattern shows after a short time. And I'm not even considering life.