Let us consider the numbers $1234$ and $6789$. For them, we see that the following equation holds:
$$6^1 + 7^1 + 8^1 + 9^1 = 30 = 1^2 + 2^2 + 3^2 + 4^2.$$
Thus, this pair of numbers is $4$-similar.

Obviously, for $k > 5$ there are no $k$-similar numbers, because there are only $10$ different digits. Let us assume that there is a pair of $5$-similar numbers $\overline{a_1 a_2 a_3 a_4 a_5}$ and $\overline{b_1 b_2 b_3 b_4 b_5}$, for which the following equation holds:
$$a_1^m + a_2^m + a_3^m + a_4^m + a_5^m = b_1^n + b_2^n + b_3^n + b_4^n + b_5^n.$$

The parity of the numbers on both sides of the equation is the same, and therefore their sum is an even number. Since these numbers are all the $10$ digits, their sum must also be even, because the parity of a number does not change when it is raised to a natural power. But the sum of all digits $0 + 1 + 2 + \cdots + 9 = 45$ is odd. The resulting contradiction shows that the maximum value of $k$ is $4$.