The two constructions are equivalent and their equivalence is based on the so-called thinning of Poisson processes.
Klenke starts from a homogenous Poisson process with a large rate $\lambda$. Amongst the times of this process, when at $x$, a relative proportion $1+q(x,x)/\lambda$ is used to jump from $x$ to $x$ and, for every $y\ne x$, a relative proportion $q(x,y)/\lambda$ is used to jump from $x$ to $y$. The jumps $x\to x$ have no effect, hence one is left with a proportion $q(x,y)/\lambda$ of jumps $x\to y$ amongst a global population of potential jump times with density $\lambda$, that is, the correct rate $q(x,y)$.
The only condition for this construction to work is $1+q(x,x)/\lambda\geqslant0$ for every $x$, that is, $\lambda\geqslant\sup\limits_x[-q(x,x)]$, hence one can choose, as many authors do, $\lambda=\sup\limits_x[-q(x,x)]$ but any larger value of $\lambda$ will do as well.
Norris's construction might be more usual hence I will not comment on it here, except to note that $\lambda$, the initial distribution in Norris, is related in no way whatsoever to $\lambda$, the positive real number in Klenke. (My impression is that Klenke's version, more elegant, is slowly replacing the other one in the probabilists' minds.)
Edit The piece of Norris's construction missing from your account is that $\Pi$ is related to $Q$ through $\Pi(x,x)=0$ for every $x$, and, for every $y\ne x$,
$$
\Pi(x,y)=\frac{q(x,y)}{q(x)}\quad\text{with}\quad q(x)=-q(x,x)=\sum_{z\ne x}q(x,z).
$$
You are describing an M/M/$\infty$ queue with arrival rate $\lambda$ and server rate $\sigma$.
The arrival process is Poisson with rate $\lambda$, so inter-arrival times are iid exponential with rate $\lambda$.
The system is reversible, so if we start out in the steady state distribution $P[N(0)=k] =\frac{(\lambda/\sigma)^k}{k!}e^{-\lambda/\sigma}$ for all nonnegative integers $k$ then the departure process is Poisson with rate $\lambda$, so inter-departure times are iid exponential with rate $\lambda$.
Edit: For any stable queue we must have the long term arrival rate equals the long term departure rate:
$$ \lim_{t\rightarrow\infty}\frac{arrive[0,t]}{t}=\lim_{t\rightarrow\infty}\frac{depart[0,t]}{t}$$
where $arrive[0,t]$ is the total number of arrivals during the interval $[0,t]$, and $depart[0,t]$ is the total number of departures during that time. Since the long term arrival rate is $\lambda$, the long term departure rate is also $\lambda$. Indeed, if not, then the queue would either be creating new jobs, or eating existing jobs.
The fact that inter-departure times are (in steady state) iid exponential is not obvious and comes from the detail equation reversible properties (which hold for every birth-death chain that is stable). It is not true if we do not start in steady state. Assuming initial steady state, your calculations could verify the marginal inter-departure time is exponential. However (assuming initial steady state) it further holds that each inter-departure time is independent of all prior ones.
The inter-event time is more complicated. In fact, even if we start in steady state, the first event is more likely to be an arrival, rather than a departure:
$$ \sum_{k=0}^{\infty} \left(\frac{\lambda}{\lambda + k\sigma}\right) \frac{(\lambda/\sigma)^k}{k!}e^{-\lambda/\sigma} > 1/2$$
The inter-event times are not identically distributed. An arrival sees the system in steady state (and then adds 1 to that) while a departure leaves the system in steady state. So the expected time to the next event, given we just had an arrival, is less than the expected time to the next event, given we just had a departure.
The fact that Poisson Arrivals See Time Averages is often called PASTA.
Best Answer
The problem gets simpler if one replace the fixed time $t$ by some random time $T_\theta$ which is independent of the Markov process and is Exponential with parameter $\lambda$.
Going back to the distribution of $Y_t$ needs to inverse a Laplace transform, which is sometimes difficult, and possible in the present situation. Observe that for every bounded Borel function $h : \mathbb{R} \to \mathbb{R}$, $$E[h(Y_{T_\theta})] = \int_0^\infty E[h(Y_t)] \theta e^{-\theta t} \mathrm{d}t.$$
I call $S_1 < S_2 < \ldots$ the jump times, and I set $S_0=0$, $D_1=S_1-S_0$, $D_2=S_2-S_1$,... and $N_t = \sup\{n \ge 0 : S_n \le t\}$. The distribution of $N_t$ is Poisson($\lambda t$), and conditionally on $N_t=n$ and $X_0=x$, the density of $(S_1,\ldots,S_n)$ is $$(s_1,\ldots,s_n) \mapsto \frac{n!}{t^n}1_{0<s_1<\ldots<s_n<t}.$$
I omit the index $\theta$ in what follows.
Let $h : \mathbb{R}^{n+1} \to \mathbb{R}$ be any bounded Borel function and $Z = h(D_1,\ldots,D_n,T-S_n)$. \begin{eqnarray*} E\big[Z1_{N_T = n}\big] &=& \int_0^\infty E\big[h(D_1,\ldots,D_n,t-S_n)1_{N_t = n}\big] \theta e^{-\theta t} \mathrm{d}t \\ &=& \int_0^\infty E\big[h(S_1,\ldots,S_n-S_{n-1},t-S_n)1_{N_t=n}\big] \theta e^{-\theta t} \mathrm{d}t \\ &=& \int_0^\infty \frac{(\lambda t)^n}{n!}e^{-\lambda t} \Big( \int_{R^n} h(s_1,\ldots,s_n-s_{n-1},t-s_n) \frac{n!}{t^n} 1_{0<s_1<\ldots<s_n<t} ds_1 \ldots ds_n \Big) \theta e^{-\theta t}\mathrm{d}t \\ &=& \int_{R^{n+1}} \theta \lambda^n e^{-(\lambda+\theta)t} h(s_1,\ldots,s_n-s_{n-1},t-s_n) 1_{0<s_1<\ldots<s_n<t} ds_1 \ldots ds_ndt \\ &=& \int_{\mathbb{R}^{n+1}} \theta \lambda^n e^{-(\lambda+\theta)(t_1+\cdots+t_n+r)} h(t_1,\ldots,t_n,r) 1_{t_1>0;\ldots;t_n>0;r>0} ds_1 \ldots dt_n dr \end{eqnarray*} Hence $$P[N_T=n] = \frac{\theta \lambda^n}{(\lambda+\theta)^{n+1}}$$ and conditionally on $[N_T=n;X_0=x]$, the random variables $D_1,\ldots,D_n,T-S_n$ are independent with distribution Exponential($\lambda + \theta$).
This enables to compute the distribution of $Y_T$.
Conditionally on $[N_T=n;X_0=x]$, $Y_T$ is the sum of $n_x := \lfloor (n+1+x)/2 \rfloor$ (respectively $\lfloor (N+2)/2 \rfloor$) independent random variables with distribution Exponential($\lambda + \theta$). Note that $n_0$ and $n_1$ depend on $n$ and $n_0+n_1=n+1$.
The distribution of $Y_T$ given $x_0=x$ is $$\sum_{n=0}^{+\infty}\frac{\theta\lambda^n}{(\lambda+\theta)^{n+1}} \Gamma(n_x,\lambda+\theta).$$ The distribution of $Y_T$ given $x_0=0$ is $$\frac{\theta}{\lambda+\theta}d\delta_0(y) + \sum_{n=1}^{+\infty}\frac{\theta\lambda^n}{(n_0-1)!(\lambda+\theta)^{n_1}} 1_{y>0} y^{n_0-1}e^{-\lambda y} dy.$$
Observe that for all $y>0$ \begin{eqnarray*} \frac{\theta\lambda^{n_1}}{(\lambda+\theta)^{n_1}} e^{-\theta y} &=& \theta e^{-\theta y} \int_0^\infty \frac{\lambda^{n_1}}{(n_1-1)!}s^{n_1-1} e^{-(\lambda+\theta) s} ds \\ &=& \int_y^\infty \frac{\lambda^{n_1}}{(n_1-1)!} (t-y) ^{n_1-1} e^{-\lambda (t-y)} \theta e^{-\theta t}dt \\ &=& \int_0^\infty 1_{t>y} \frac{\lambda^{n_1}}{(n_1-1)!} (t-y) ^{n_1-1} e^{-\lambda (t-y)} \theta e^{-\theta t}dt \end{eqnarray*} Hence, dividing both sides by $\theta$ and inverting Laplace transform yields that the distribution of $Y_t$ given $X_0=0$ is $$e^{-\lambda t} d\delta_0(y) + \sum_{n=1}^{+\infty} \lambda^{n}e^{-\lambda t} \frac{1}{(n_0-1)!(n_1-1)!} 1_{0<y<t} y^{n_0-1}(t-y) ^{n_1-1}dy,$$ namely $$e^{-\lambda t} d\delta_0(y) + \sum_{n=1}^{+\infty} \frac{(\lambda t)^{n}e^{-\lambda t}}{n!} \frac{n!}{(n_0-1)!(n_1-1)!}1_{0<y<t}\frac{1}{t^n} y^{n_0-1}(t-y) ^{n_1-1}dy.$$ Conditionally on $[N_t=n;X_0=0]$, $Y_t/t$ follows a Beta distribution with parameters $n_0$ and $n_1$.