There is a continuous time version of this problem that sheds some more light on this. The discrete time result follows by choosing piecewise constant processes $k$. 

It follows from [1, theorem 5.1]  that
$$\tag{$1$}\int_0^{S_t} k_s dN_s$$
is a Poisson process. Here $k$ is a process taking only the values 0 and 1 that is adapted to the natural filtration of $N$, $T$  is the finite time change (see [3]) given by
$$T_t = \int_0^t k_s ds,$$ 
$S$ is the generalized inverse time change of $T$ given by
$$S_t = \inf\ \{ s>0:T_s >t \} ,$$
and $N$ is a Poisson process with intensity $\lambda$.
The result (1) has been proven earlier in [2, théorème 2'], but I find [1] more accessible. 

It follows from the law of large numbers that
$$\frac{1}{t} \int_0^{S_t} k_s dN_s \to \lambda \quad \text{a.s.}$$
Applying the time change $T$ then yields the desired formula
$$\frac{1}{T_t} \int_0^{t} k_s dN_s \to \lambda \quad \text{a.s.}$$

Note: $k$ can not be replaced by a process with values in $\mathbb R$ without making additional assumptions on the integrator $N$. It has been shown in [4] that $N$ needs to be an $\alpha$ stable Levy process. The proof is much more instructive than [1] or [2]. It is based on a property of the cumulant process $\mathcal K^N(k)$ of $N$ in the process $k$.
One has 
$$\mathcal K^N(k)_t = \int_0^t \kappa(k_s) ds $$
for some function $\kappa$. The $\alpha$ stability of $N$ implies that 
$$\kappa(k x)=\lvert k\rvert^\alpha \kappa(x),\tag{$2$}$$
and this property is responsible for equation (1) to hold.
Now it is obvious that (2) holds if $k$ takes only the values 0 and 1. Thus (1) is valid for all Levy processes.

[1] Kallenberg, Random time change and an integral representation for marked stopping times.

[2] Meyer, Démonstration simplifiée d’un théorème de Knight.

[3] Kobayashi, Stochastic Calculus for a Time-Changed Semimartingale.

[4] Kallsen and Shiryaev, Time Change Representations of Stochastic Integrals.