See this answer for how accurately the antenna must be pointed. That accuracy is not a function of the distance. It is only a function of the size of the antenna and the wavelength of the transmission. The antenna on New Horizons has the same required pointing accuracy at Pluto as it did at Jupiter. What changes is the received power at Earth, and therefore the maximum data rate. That goes down with the square of the distance.
The size of the antenna and the wavelength determine the tightest possible angle that the beam can be focused to. Once you have that angle, you just need to keep Earth somewhere in there. The angular size of the Earth at the distance of the spacecraft is generally much, much smaller than the beam width of the antenna. So only a tiny fraction of the power from the antenna falls on the Earth. An even tinier fraction falls on the receiving antenna on the Earth.
Antennas are pointed using star trackers and an on-board model of the position of Earth relative to the spacecraft on its trajectory. Star trackers are cameras that accurately determine the attitude of the spacecraft by matching star field patterns. Just a few bright stars in the field of view will do the trick. Typical accuracies are a few arcseconds. Ball has a 0.1 arcsecond tracker.
Yes, Mars Orbiters and all spacecraft have to change the pointing of their antennas over time to track the Earth. Both the Earth and the spacecraft are moving in inertial space (i.e. relative to the stars the star tracker is tracking), so the direction to point the antenna is always changing.