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.