Since the sum of digits of an integer divisible by $k-1$, is divisible by $k-1$, too, $(k-1)^3$ divides all the numbers obtained after the second step. $(k-1)^3$. On the other hand, if $a = \overline{a_n a_{n-1} \dots a_0(k)}$, $n \ge 4$ or $a_3 \ge 2$, $n = 3$, then

$$\begin{align*} a - (k-1)^2 (a_n + a_{n-1} + \dots + a_0) &\ge 2(k^3 - (k-1)^2) - a_1((k-1)^2-k) - a_0((k-1)^2-1)) \\ &\ge 2(k^3 - (k-1)^2) - (k-1)(2(k-1)^2 - k - 1) = 5k^2 - 2k - 1 > 0. \end{align*}$$
This shows that we shall get a number of the form $a = \overline{a_3 a_2 a_1 a_0(k)}$, where $a_3 = 0, 1$. The next number is
$$(k-1)^2(a_3 + a_2 + a_1 + a_0) \le (k-1)^2(1 + 3(k-1)) < 4(k-1)^3.$$

Hence this number is $(k-1)^3$, $2(k-1)^3$ or $3(k-1)^3$. Note that
$$(k-1)^3 = \overline{k-3,2,k-1}_{(k)} \rightarrow 2(k-1)^3, \quad k > 2,$$
$$2(k-1)^3 = \overline{1,k-6,5,k-2}_{(k)} \rightarrow 2(k-1)^3, \quad k > 5,$$
$$3(k-1)^3 = \overline{2,k-9,8,k-3}_{(k)} \rightarrow 2(k-1)^3, \quad k > 8.$$
Since $3.5^3 = \overline{1423}_{(6)} \rightarrow 10.5^2 = 2.5^3$, $3.6^3 = \overline{1614}_{(7)} \rightarrow 12.6^2 = 2.6^3$ and $3.7^3 = \overline{2005}_{(8)} \rightarrow 7.7^2 = 7^3 \rightarrow 2.7^3$, we conclude that if $k > 5$, then the numbers are equal to $2(k-1)^3$ from some point onwards.