If a multiplier automaton is in a state $\sigma$ after reading prefixes $u(i),v(i)$ of the input words $u,v$ then the group element $u(i)^{-1}v(i)$ is uniquely determined by $\sigma$. So I guess a crude upper bound for the fellow-travelling constant $k$ is twice the maximum number of states of any of the multiplier automata. Since the shortlex automatic structure enables you to reduce any word to shortlex normal form, it is certainly possible (and straightforward) to use it to compute the possible the length in the group of the elements $u(i)^{-1}v(i)$ determined by each state, and thereby determine $k$ exactly.
I don't understand Question 2. If you are given the shortlex automatic structure, then you don't need $k$ to compute the minimal number of states of the automata, you can compute them directly from the automata themselves using the standard algorithm (Myhill-Nerode?) for this.
I have no idea what source to recommend for a non-mathematician. Presumably you are already familiar with "Word Processing in groups" by Epstein et al? There are alternative sources but I don't think any of them are more elementary.
Added later. For the new question 2, I don't believe that there is any straightforward way to do this. Of course, if a group (defined by a finite presentation) is shortlex automatic, then it is possible to compute the automatic structure, and knowing the value of $k$ could make that a little easier, because it would help you know when to stop certain searches, but I am doubtful whether it would really help much in practice.
You could derive an upper bound on the numbers of states from $k$, but it would be doubly exponential in $k$, because you can construct the word acceptor with each state being a subset of the set of words of length at most $k$, whereas the states of the multipliers consist of pairs $(\sigma,u)$ with $\sigma$ a state of the word acceptor and $u$ a word of length at most $k$. It is possible that there is a simply exponential bound, but perhaps not. The algorithms that construc the automatic structure have complexity doubly exponential in $k$ in theory. Fortunately, in practice they do seem to work. This is mainly because critical quantity is not the maximum length $k$ of the wors that arise as $u(i)^{-1}v(i)$ in the notation above, but the total number of such words, which is typically much smaller than the total number of words of length $k$.
So I guess the real answer is that $k$ is not the best number to use for this purpose, and I think that answers Question 3 as well.
Question 4 is interesting. In the paper
P. Papasoglu, Strongly geodesically automatic groups are hyperbolic.
Invent. Math., 121(2):323-334, 1995.
Papasoglu proved that if geodesic bigons in the Cayley graph are unformly thin, then the group is hyperbolic. The thinness constant ($k'$ say) of geodesic bigons is the fellow-travelling constant for all geodesic bigons rather than just those labelled by shortlex least words, so it could be a little larger than your $k$, but typically not much so.
I had a student a while ago who went through Papasoglu's proof and tried to bound the thinness of geodesic triangles constant $\delta$ in temrs of $k'$, but again the best bound he could come up with was doubly exponential in $k'$. In all of the examples I have ever seen, we seem to get things like $\delta = k'+2$, so it is frustrating not to be able to get a better bound. Papsoglu told me once that he had also tried to do this without success.
