Yes. To a large extent, the positions of the stars are fixed with respect to each other. It's just the Earth that moves around. You're trying to get latitude, which you can get from the altitude of a star above the southern horizon, and longitude, which you get from when the star passes east to west. Choosing another star doesn't get you out of having to measure which direction is down. The "which direction is down" question is the answer to "where am I on Earth" - the telescope and timer are just there to set your frame of reference.
Sextants used at sea find altitude angles by measuring between the stars(or other astronomical objects) and the horizon. There is a correction that can be applied to account for wave height as it affects the "eye height." Azimuth can be found by measuring against stars that are low in the sky, but most of the time you do not need this for sea navigation. "Down" is inferred as the shortest path between a star and the horizon. It takes a bit of practice to get a good measurement from a rolling boat, but it is skill anyone can learn.
At sea the fact that "down" is perpendicular to the horizon is useful, because the horizon is pretty much a straight line. On land this is irrelevant because the horizon is rarely flat on land.
You would suspend your measuring apparatus in a device that absorbed or heavily dampened the motion of the waves (like gas struts, or something similar).
