This is partly a question of 'limiting magnitude' - the faintest magnitude that is visible using a particular instrument, or in this case, just the eye.
+6 - maybe +6.5 - magnitude is sometimes used as a baseline expectation of what can be seen in dark skies sites.
The most distant star that can easily be seen is Deneb. It is actually quite bright, at brighter than +2 Magnitude, but is (probably) 1425ly away. So though it is at quite some distance, it's luminosity means that actually, it isn't limiting magnitude that is at play.
There are stars much further away that are at the barely perceivable limit, and seeing them will depend on conditions. The +4 mag mu Cephei is probably fairly achievable, at 5900ly, and V762 in Cassiopeia is about +6 mag and maybe 16000ly, which would probably be the record if you can actually see it, but you'll need special conditions.
When it comes to galaxies, Andromeda is 2500000ly away, and +3.4, very visible and much further away than any individual star. If you have good conditions, the +5.7 mag M33 is slightly further away at 2900000ly, but it would be much harder to see.
While the generally accepted limit is maybe +6.5, some people claim to have seen to +8. If it is possible, M83 is 14700000ly away at +8.2, with naked-eye claims reported.