The greedy algorithm is optimal.
The simple observation is that any optimal $k$ digits to remove must contain the rightmost digit in the initial non-decreasing digits of A, or one of its equivalents.
Given an $n$-digit number $A=a_{n-1}a_{n-2}\cdots a_1a_0$, where each $a_i$ is a digit, let $a_t$ be the rightmost digit of $A$ such that $a_n, a_{n-1}, \cdots, a_t$ is non-decreasing. Let $r$ be the number of all digits that are equal to $a_t$ from $a_t$ to its left. In other words, the digits of $A$ are classified as displayed in the following illustration for some integer $t$ and $r$, where $ a_t>a_{t-1}$ and $a_{t+r}<a_{t+r-1}=\cdots=a_{t+1}=a_t$. Note that if there is only one digit in $A$, it is $a_t$ with $t=0$ and $n=r=1$.
$$\begin{aligned}
A&=\overbrace{a_{n-1}a_{n-2}\cdots a_{t+r}\ \underbrace{a_{t+r-1}\cdots a_{t+1}a_t}_{r\text{ copies of }a_t}}^{\text{longest non-decreasing}}\ a_{t-1}\cdots a_0\\
\mu(A)&=a_{n-1}a_{n-2}\cdots a_{t+r}\{r\text{$-$}1\text{ copies of }a_t\}a_{t-1}\cdots a_0\\
\end{aligned}$$
Define integer $\mu(A)$ as shown above, which is $A$ but with one of $a_{t+r-1},\cdots,a_{t+1}, a_t$ removed. For example, $\mu(1214532)=114532$, $\mu(112)=11$, $\mu(40012)=0012$ and $\mu(0012)=001$. Note that the value of $\mu(A)$ does not depend on the number of leading $0$'s in $A$. For example, $\mu(001332)=00132$${}=\mu(1332)=132$.
Lemma. $\mu(A)$ is the smallest number that is $A$ with one digit removed.
Proof. Easy.
Let $G$ be the greedy algorithm. The lemma above says $G(A,k)=\mu^k(A)$.
Claim. For all non-negative integer pairs $(A,k)$, $G$ is optimal, i.e., $G$ returns the smallest number.
Proof. Let $P(k)$ be the proposition that $G(I,k)$ will return the smallest number for all integer $I$ of more than $k$ digits. The claim is $P(0)$, $P(1)$, $P(2)$, $\cdots$ are true.
Use induction on $k$. The base case, when $k=0$, is trivially true.
Assume $P(k)$, the induction hypothesis, is true. Let $A$ be an integer and $S$ be some $k+1$ digits of $A$ such that $B$, which is $A$ with digits in $S$ removed, is as small as possible. We will prove $G(A,k+1)\le B$, i.e, $P(k+1)$ is true, thus completing the induction.
Let us reuse the classification above of the digits of $A$, i.e., they start with the non-decreasing sequence $a_{n-1}, a_{n-2}, \cdots, a_{t}$ with $a_{t}>a_{t-1}$ and $ a_{t+r}<a_{t+r-1}$.
$S$ does not contain any digit in that sequence.
This cannot happen, since we can get a number smaller than $B$ by removing $a_{t}$ and arbitrary $k-1$ digits to the right of $a_{t-1}$.
$S$ does contain one of the digits in that sequence, say, $a_\ell$.
$S$ does not contain any one of $a_{t+r-1}$, $\cdots$, $a_{t+1}$, and $a_t$.
We can modify $S$ by substituting $a_t$ for $a_\ell$. The removal of the digits in the modified $S$ will return a number smaller than $B$. So this case cannot happen, either.
Otherwise, WLOG, let $a_\ell$ be one of $a_{t+r-1}$, $\cdots$, $a_{t+1}$, and $a_t$.
The lemma above tells us that $A$ with $a_\ell$ removed is $\mu(A)$. Let $S_-$ be $S$ without $a_\ell$. So $S_-$ are some $k$ digits of $\mu(A)$. We have the following diagram, where the arrow reads "become". $\require{AMScd}$
\begin{CD}
\mu(A),k@>\text{greedy algorithm}>> G(\mu(A), k)\\
@| \\
\mu(A),k@>{\text {remove elements in }S_-}>> B\\
\end{CD}
The induction hypothesis ensures $G(\mu(A), k)\le B$. Since $G(A,k+1)=G(\mu(A), k)$, we are done.
Exercise. (A couple of minutes or more) Given two positive integers $k\lt n$ and an $n$-digit integer $A>0$, how can you remove $k$ digits from $A$ such that the resulting integer is the biggest one? Explain the greedy algorithm. Prove it is correct.
The exercise shows that the greedy algorithm is still optimal in the original problem when $A$ is negative.
