We've been mocking Starship because it's not going to fly to another star, but according to this solar system delta v map it only takes 5.63 km/s from a Moon transfer orbit to Sun escape velocity. A 130 t dry (with 10 t payload) and 1330 t wet Starship with 380 s Isp has 8666 m/s, so it'd have 3036 m/s excess velocity. It could also fly by Jupiter for extra speed and/or a plane change.
Which star could Starship fly to soonest? Not just pass through its Hill sphere, but like fly by at 1 AU (or theoretically collide with it). Proxima centauri is about 4.2 ly away. At 3 km/s it would take 420 ka (kiloanni) to travel 4.2 ly. In 420 ka any currently near stars are long gone (nearest stars flying by). So the question is, which star could Starship realistically fly to, be there when Starship is there. Bonus question: What's the relative speed in the encounter?
PS: Someone suggested retanking starship with expendable tankers en route to Jupiter and gain 20 km/s with a burn at Jupiter. Much more expensive, but this is just theoretical and it's within specs of Starship and it seems to get us within the time frame of the passing stars diagram, so we can also consider this variant.