The solution to get Starship and Shuttle beyond LEO is the same: either use up the fuel required for landing and expending the vehicle or orbital refueling.
The difference is that Starship is so cheap it makes both of those options feasible. Shuttle's reusability was supposed to make it cheap, but it ended up costing $1.5 billion per flight.
https://arstechnica.com/science/2019/08/rocket-scientist-say...
There is another thing sets apart Starship from other launch systems: relatively wide availability/manufacturability of its fuel outside of Earth. You won't find kerosene or hypergols on Mars or Ganymedes, but methane can be produced fairly straightforwardly there.
Hydrogen is notoriously tricky to even keep in one place, much less pipe across some distance.
But that's exactly what people believed about the space shuttle before it launched as well. Let's wait to see Starship actually work before predicting it will be enormously cheap. As it stands, that cheapness is entirely predicated on a completely unrealistic level of reusability (multiple launches per day with the same rocket, when even Falcon 9 requires weeks or months between launches of the same rocket).
You have full powered engines in orbit on Starship, "just" need to fuel them :)