Let $a$ be the first digit of the string, and let $b$ be
the value of the remaining digits. Let's prove that the
operation is reducing with respect to the lexical order of
$\langle a,b\rangle$, which is one version of interpreting
your phrase "double induction."
First, note that the operation of inserting the $0$ to the
right of the leading digit affects neither the value of $a$
nor $b$.
Next, note that if $b$ is all zero but $a$ is not $0$, then
the operation will end up with $a$ being reduced, because
when you subtract one, you will have to borrow from $a$,
thereby reducing. Thus, the operation will result with a
string having lower $\langle a,b\rangle$ in the lexical
order.
If $b$ is not all zero, however, then the operation will
end up with the $b$ value being value $1$ less (despite the
extra $0$), and so will reduce $\langle a,b\rangle$ in the
lexical order.
Since the lexical order on $\mathbb{N}\times\mathbb{N}$ is a well-order, it follows that
the operation must eventually hit all $0$s.
The argument shows that you can insert any number of $0$s, rather than just one $0$ at each step, although if you insert more, then it will take longer to get to the all $0$ string, since when you borrow, you will get more $9$s.
You seem to have misplaced a quantifier. It is true, as you said, that $p(k)\implies p(k+1)$ is logically equivalent to $(\neg p(k))\lor(p(k)\land p(k+1))$, and therefore the second premise of the induction axiom, $(\forall k)\,[p(k)\implies p(k+1)]$, is equivalent to $(\forall k)\,[(\neg p(k))\lor(p(k)\land p(k+1))]$. But then you went from this statement to
$$
[(\forall k)\,\neg p(k)]\lor[(\forall k)\,[p(k)\land p(k+1)].
$$
This "distribution of $\forall$ over $\lor$ is not valid. The correct formula allows the possibility that $\neg p(k)$ holds for some values of $k$ and $p(k)\land p(k+1)$ holds for all the other values of $k$. The transformed formula requires the same alternative to hold for all $k$, and this is something quite different.
Best Answer
It depends on the statement you want to prove.
You can see the statement $$\forall n\in\mathbb N, \forall k\in\{1,\dots,n\},P(n,k)$$ as $$\forall n\in\mathbb N,Q(n)$$ where $$Q(n)=\forall k\in\{1,\dots,n\},P(n,k).$$
Then you show that $Q(1)$ is true and that $$\forall n\in\mathbb N,Q(n)\implies Q(n+1)$$ to conclude.