Obviously, the sequence $(a_n)_{n=1}^{\infty}$ is increasing until the first term with the zero digit occurs and is constant following this term. Our aim is to find such values $a$ and $k$ that the zero digit first occurs in $a_{2009}$. We will solve the problem in general – given an integer $m > 4$, we present $a$ and $k$ such that the zero digit first occurs in $a_m$.
Set
$$a = \frac{10^{2m-5} - 1}{9} = \underbrace{11\dots1}_{2m-5 \text{ ones}}, \quad k = 10^{m-3} + 4 = 1 \underbrace{00\dots0}_{m-4 \text{ zeros}} 4.$$

Then we have
$$a_1 = a = \underbrace{11\dots1}_{2m-5}$$
$$\varrho(a_1) = 1.$$
$$a_2 = a_1 + k = a_1 + \underbrace{100\dots04}_{m-1} = \underbrace{11\dots12}_{m-3} \underbrace{11\dots15}_{m-4}$$
$$\varrho(a_2) = 10.$$
$$a_3 = a_2 + 10k = a_2 + \underbrace{100\dots040}_{m-4} = \underbrace{11\dots122}_{m-4} \underbrace{11\dots155}_{m-5}$$
$$\varrho(a_3) = 100.$$
$$a_i = a_{i-1} + 10^{i-2}k = \underbrace{11\dots122\dots2}_{m-1} \underbrace{11\dots155\dots5}_{m-1}$$
$$\varrho(a_i) = 10^{i-1}.$$
$$a_{m-2} = a_{m-3} + 10^{m-4}k = \underbrace{122\dots255\dots5}_{m-3}$$
$$\varrho(a_{m-2}) = 10^{m-3}.$$
$$a_{m-1} - a_{m-2} + 10^{m-3}k = \underbrace{100\dots0}_{m-4} \underbrace{100\dots0}_{m-3} \underbrace{22\dots2655\dots5}_{m-3}$$
$$\varrho(a_{m-1}) = 6 \cdot 10^{m-3}.$$
$$a_m = a_{m-1} + 6 \cdot 10^{m-3}k = \underbrace{600\dots0}_{m-5} \underbrace{2400\dots0}_{m-3} \underbrace{822\dots25055\dots5}_{m-5}$$
$$\varrho(a_m) = 0.$$

Second solution. Put
$$a = \underbrace{611\dots1}_{2007} \quad \text{and} \quad k = \underbrace{33\dots34}_{2007} = \frac{1}{6} \cdot \underbrace{200\dots04}_{2007}$$

Then we have
$$\begin{align*} a_1 &= \underbrace{6 \ 11 \dots 1}_{2007}, & \varrho(a_1) &= 6, & k\varrho(a_1) &= \underbrace{2 \ 00 \dots 0 1}_{2007} \\ a_2 &= \underbrace{26 \ 11 \dots 1 5}_{2006}, & \varrho(a_2) &= 60, & k\varrho(a_2) &= \underbrace{2 \ 00 \dots 0 40}_{2007} \\ a_3 &= \underbrace{226 \ 11 \dots 1 55}_{2005}, & \varrho(a_3) &= 600, & k\varrho(a_3) &= \underbrace{2 \ 00 \dots 0 400}_{2007} \\ a_4 &= \underbrace{2226 \ 11 \dots 1 555}_{2004}, & \varrho(a_4) &= 6000, & k\varrho(a_4) &= \underbrace{2 \ 00 \dots 0 4000}_{2007} \\ & & & & \\ a_{t+1} = \underbrace{22 \dots 2 6 \ 11 \dots 1 55 \dots 5}_{2007-t}, & \varrho(a_{t+1}) &= \underbrace{6 \ 0 \dots 0}_{t}, & k\varrho(a_{t+1}) &= \underbrace{2 \ 00 \dots 0 4 \ 00 \dots 0}_{2007} \\ & & & & \\ a_{2007} = \underbrace{22 \dots 2 6 \ 15 \dots 5}_{2006} & \varrho(a_{2007}) &= \underbrace{6 \ 0 \dots 0}_{2006}, & k\varrho(a_{2007}) &= \underbrace{2 \ 00 \dots 0 4 \ 00 \dots 0}_{2007} \\ a_{2008} = \underbrace{22 \dots 2 6 \ 55 \dots 5}_{2007} & \varrho(a_{2008}) &= \underbrace{6 \ 0 \dots 0}_{2007}, & k\varrho(a_{2008}) &= \underbrace{2 \ 00 \dots 0 4 \ 00 \dots 0}_{2007} \\ a_{2009} = \underbrace{22 \dots 2 30 \ 55 \dots 5}_{2007} & \varrho(a_{2009}) &= 0, & k\varrho(a_{2009}) &= 0 \end{align*}$$
and obviously $a_{2009}, a_{2010}, a_{2011}, \dots$