This answer concerns Q1, showing convergence of the largest eigenvalues of $G_{k}$ to the exponential growth rate of walks on the infinite graph. For the infinite graph, let $g(n,m)$ be the number of walks of length $n\geq0$ starting at $1$ and ending at $m$ (possibly going to vertices higher than $m$ before ending at $m$). Considering arcs arriving at vertex $m>1$ gives $g(n,m)=g(n-1,m-1)+g(n-1,n)+g(n-1,2m)$, and we have the starting conditions
$g(0,1)=1;$ $g(0,m)=0,m>1;$ $g(1,1)=1;$ $g(n,1)=g(n-1,1)+g(n-1,2),~n>1$.

Evaluating the first few rows with a recursive procedure gives the following table (rows indexed by $n$, columns indexed by $m$).

$$
\begin{array}{c|ccccccc} 
& 1 & 2 & 3 & 4 & 5 & 6 & 7\\\hline
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
2 & 2 & 2 & 1 & 0 & 0 & 0 & 0\\
3 & 4 & 4 & 3 & 1 & 0 & 0 & 0\\
4 & 8 & 9 & 7 & 4 & 1 & 0 & 0\\
5 & 17 & 21 & 16 & 11 & 5 & 1 & 0\\
6 & 38 & 49 & 38 & 27 & 16 & 6 & 1
\end{array}
$$

The row sums give the sequence

$$
r=(1,2,5,12,29,71,175,432,1066,2630,6493,16049,39715,98361,243723,604043,1497223,3711420,9200960,22812509,...),
$$

whose exponential growth rate is of interest. This may be evaluated as $\lim_{n\rightarrow\infty}r(n)/r(n-1)$. For example, an estimate (determined from the algorithm below) is $r(500)/r(499)=2.482146221045796473951094418$ (differing in the last two digits from $r(499)/r(498)$).

Now consider the finite graph $G_{k}$. As usual, the number of walks of length $n$ between vertices $i$ and $j$ is given by the $i,j$ entry of $(A_{k})^{n}$, where $A_{k}$ is the adjacency matrix. The number of walks of length $n$ from vertex $1$ to $m$, $m=1,\ldots,k$ is the first row of $(A_{k})^{n}$. The lower Hessenberg form means that successive powers increase the number of nonzero superdiagonals by $1$ and the first row first becomes all nonzero at $n=k-1$. These first rows are in agreement with those in the table above for the infinite graph, since *one cannot progress beyond vertex $k$ with a walk of length less than $k$*. Therefore the row sums of the first rows of the powers $(A_{k})^{n}$, $n=1,\ldots,k-1$ agree with the row sums for the infinite graph. For higher powers the number of walks departs from the number with that length in the infinite graph, of course being lower,
$$
r_{k}(n)=r(n),~0\leq n\leq k-1
$$
$$
r_{k}(n)\leq r(n),~n>k-1
$$
For example for $k=10$ the row sums are

$$
r_{10}
=(1,2,5,12,29,71,175,432,1066,2630,6492,16037,39634,97953,242006,597634,1475223,3640313,8981042,22154279,...),
$$
showing agreement to $n=9$ $(2630)$.

The growth rates for the sequences for each $k$ can be found using a generating function approach. We mark walk steps with $z$, then $(zA_{k})^{n}$ enumerates walks of length $n$, and for all lengths we have $\sum_{n=0}^{\infty}
(zA_{k})^{n}=(I_{k}-zA_{k})^{-1}$, where $I_{k}$ is the $k\times k$ identity matrix.
We want the sum of the first row, so the generating function is $e_{1}^{T}(I_{k}-zA_{k})^{-1}e$, where $e$ is the all-ones vector and $e_{1}=[1,0,0...0]$. Expanding as a power series gives a series with the coefficients above. For a rational function generating function as here, the growth rate is found as the reciprocal of the distance of the nearest pole from the origin on the positive real axis. To evaluate this note that
$$
e_{1}^{T}(I_{k}-zA_{k})^{-1}e=\frac{e_{1}^{T}\operatorname{Adj}(I_{k}-zA_{k})e}{\det(I_{k}-zA_{k})}
$$

Let $z_{\min}$ be the smallest root of the polynomial $\det(I_{k}-zA_{k})$, then $1/z_{\min}$ is the maximum root of $\det(tI_{k}-A_{k})$, $t=1/z$, i.e., the maximum eigenvalue of $A_{k}$ gives the exponential growth rate of walks starting from 1; the same asymptotics apply as for walks between any two vertices $i$ and $j$. The maximum eigenvalues form a monotone increasing sequence as $k$ increases. To see this, note that for nonnegative matrices,
the spectral radius of a principal submatrix must be less than or equal to that of the matrix, so $\rho(A_{k})\leq\rho(A_{k+1})$, where in this case the spectral radius is the maximum eigenvalue. The maximum row sum of each of the matrices is $3$, which is an upper bound for the spectral radius, and so a limit exists for the monotone sequence.

To show this limit is the growth rate on the infinite graph, consider the algorithm for generating $r(n)/r(n-1)$ for arbitrary $n$ based on the above-noted agreement between $r$ and $r_{k}$. Choose $k=n+1$. Then $r(n)=e_{1}^{T}\left( A_{k}\right)^{n}e$, or $r(n)$ is the first entry of $\left(A_{k}\right)^{n}e=u_{n}$; similarly for $r(n-1)$ (using the same $k$). In the power method for finding the largest eigenvalue, one chooses an initial vector $x_{0}$ and iterates $x_{j+1}:=A_{k}x_{j}$ to find the eigenvector corresponding to the largest eigenvalue. If we choose $x_{0}=e$ and omit the customary renormalization during the iterations, then $r(n-1)$ and $r(n)$ are the first entries of the $(n-1)$ th and $n$th iteration eigenvectors. Since $u_{n}=Au_{n-1}\approx\lambda_{\max}u_{n-1}$, $r(n)/r(n-1)$ is an estimate of $\lambda_{\max}$ for $A_{n+1}$.The value of $r(500)/r(499)$ was given above; $\lambda_{\max}$ for $A_{501}$ is $2.482146221045796473951094505$ (a difference of $10^{-25}$).

So the sequence of $r(n)/r(n-1)$ that gives the growth rate on the infinite lattice is essentially the same as the sequence of (approximate) maximum eigenvalues of the $A_{k}$, and has the same limit.

**Notes:**

1. The argument needs work for a formal proof. The approximations to the maximum eigenvalues presumably become sufficiently more accurate at higher $n$.

2. The power method requires the maximum eigenvalue to be greater in magnitude that the others. In addition to irreducibility we need the $A_{k}$ to be primitive; the nonzero diagonal entries are sufficient for this. The initial vector $x_{0}$ cannot be orthogonal to the left eigenvector for $\lambda_{\max}$; since both these vectors are positive this is also satisfied.