Where concepts break
There is no such thing as a parallel transport isometry in hyperbolic geometry. You can have a translation along a geodesic axis, but points off that axis will be transported along a curve. The curve has constant distance to the axis, but is itself not a geodesic. Therefore, your concept of a vector as a combination of length and direction won't translate to the hyperbolic plane.
Transformations as building blocks
The other formulation you use in that comment, “what takes you from A to B”, is more readily applicable. You can think of vectors as prepresentants for specific isometries, and you can think of the grid points as the oribit of a given point under these isometries. You can come up with isometries of the hyperbolic plane which yield similar results. Instead of a vector you'd describe this class the way you'd describe an arbitrary isometry of the hyperbolic plane. How you do that very much depends on preferences and the model you employ, but for the Poincaré disc model you'd probably use 4 complex numbers to describe a Möbius transformation. You can reduce this to 4 real numbers by using the upper half plane, or by expliting the specific class of possible Möbius transformations, and perhaps even 3 numbers only if you dehomogenize in some way. Expressed in $\mathbb{CP}^1$, the complex projective line, concatenation of Möbius transformations is simply a multiplication of matrices, so that's what would become of your vector addition.
Congruent polygons
Or you can think of integer grid in the Euclidean plane as a grid made up from squares, and generalize that. In general you have regular $m$-gons, and at each corner $n$ of them meet. Take $2m+2n<mn$ and you are in hyperbolic geometry. The numbers $m$ and $n$ define all the angles and therefore all the lengths as well, as there isn't a global scaling isometry in hyperbolic geometry either. This paragraph will give you a good intuition as to what grids can look like, while the paragraph before this gives you an idea of how to do computations. Together I believe these two concepts should give you as good a toolbox as you can hope for, given the nature of the question and the time it has remained unanswered.
Representation as a group
Here is something I do in practice: take the polygons described above, and split them along their axes of symmetry to obtain elementary right triangles. Now you can take a single of these triangles, label its edges $a$, $b$ and $c$, and obtain any triangle from your tessalation using a combination of these reflections (see my current avatar). This corresponds to a finitely presented group:
$$\left<a,b,c\;\middle|\;1=a^2=b^2=c^2=(ab)^2=(bc)^m=(ca)^n\right>$$
After that, you can do computations in that group. The problem of comparing two labels corresponds to the word problem in this group, which can in fact be solved by computing a canonical form using a deterministic finite state automaton obtained from a string rewrite system by applying the Knuth-Bendix procedure. There might be a slight modification required if you want to label vertices instead of triangles, but in general this approach should work for the tessalations you referred to (i.e. those by Don Hatch). I'm writing up large portions of this as part of my PhD, so I'll likely post a follow-up on this one day.
Consider the full great circle that your $Q$ to $R$ arc is part of. There are two points (poles) which are each 90 degrees of arc from every point on the great circle. (You can find these points by forming a 90-90-x triangle from your arc segment.) Choosing the point which is on the same hemisphere as your point $P$, there is an arc from this pole, through $P$, to the great circle. Since the length of this arc is 90 degrees, the distance from $P$ to the great circle is the complement of the distance from the pole to $P$.
Determining the distance from $P$ to the actual arc then is just a matter of determining if the intersection point is between $Q$ and $R$, and if not, determining the distances from $P$ to $Q$ and $R$ to get the minimum.
A note to anyone who objects to my use of degrees: sorry, but I use my spherical trig on the actual earth, where lat and long are still measured in degrees. And yes, I am aware it is not a true sphere, but that is a separate topic.
Best Answer
I imagine what you want is the half-hyperboloid model in $\mathbf R^{n+1}$ with the Lorentz metric. So, the set is $x_{n+1} >0$ in $$ x_1^2 + x_2^2 + \ldots + x_n^2 - x_{n+1}^2 = -1.$$ There is a useful distinguished North Pole at $(0,0,0,\ldots,0,1).$ Geodesics, at unit speed, going through the North Pole are rotations of $$(\sinh t,0,0,\ldots,0,\cosh t). $$ Indeed, all isometries preserve the ambient metric. Let's see, all geodesics are the intersection of a 2-plane passing through the origin with the hyperboloid. As a result, there is a isometry to the Beltrami-Klein model given by central projection around the origin, to the $n$-ball $$x_{n+1} =1, \; \; x_1^2 + x_2^2 + \ldots + x_n^2 < 1. $$ Finally, an isometry of Beltrami-Klein to the Poincare $n$-ball model is given by vertical projection to the lower hemisphere of the ordinary $n$-sphere in $\mathbf R^{n+1}$ followed by stereographic projection around the North Pole to the Poincare $n$-ball $$x_{n+1} =0, \; \; x_1^2 + x_2^2 + \ldots + x_n^2 < 1. $$ The diagram for some of these maps is page 255, figure 246 of Hilbert and Cohn-Vossen, Geometry and the Imagination. However, Hilbert makes the disk containing the final Poincare model have radius 2, I have altered things a little to get radius 1.
This ought all to be in Spivak's five-volume book.