One needs to show that if $\mathrm{rank}(B)=k$, then $\|A-B\|_2\geq\|A-A_k\|_2$. This can be done as follows.
Since $\mathrm{rank}(B)=k$, $\dim\mathcal{N}(B)=n-k$ and from $$\dim\mathcal{N}(B)+\dim\mathcal{R}(V_{k+1})=n-k+k+1=n+1$$ (where $V_{k+1}=[v_1,\ldots,v_{k+1}]$ is the matrix of right singular vectors associated with the first $k+1$ singular values in the descending order), we have that there exists an
$$x\in\mathcal{N}(B)\cap\mathcal{R}(V_{k+1}), \quad \|x\|_2=1.$$
Hence
$$
\|A-B\|_2^2\geq\|(A-B)x\|_2^2=\|Ax\|_2^2=\sum_{i=1}^{k+1}\sigma_i^2|v_i^*x|^2\geq\sigma_{k+1}^2\sum_{i=1}^{k+1}|v_i^*x|^2=\sigma_{k+1}^2.
$$
From $\|A-A_k\|_2=\sigma_{k+1}$, one gets hence $\|A-B\|_2\geq\|A-A_k\|_2$. No contradiction required, Quite Easily Done.
EDIT An alternative proof, which works for both the spectral and Frobenius norms, is based on the Weyl's theorem for eigenvalues (or more precisely, its alternative for singular values): if $X$ and $Y$ are $m\times n$ ($m\geq n$) and (as above) the singular values are ordered in the descreasing order, we have
$$\tag{1}
\sigma_{i+j-1}(X+Y)\leq\sigma_i(X)+\sigma_j(Y) \quad\text{for $1\leq i,j\leq n, \; i+j-1\leq n$}
$$
(this follows from the variational characterization of eigen/singular values; see, e.g., Theorem 3.3.16 here).
If $B$ has rank $k$, $\sigma_{k+1}(B)=0$.
Setting $j=k+1$, $Y:=B$, and $X:=A-B$, in (1) gives
$$
\sigma_{i+k}(A)\leq\sigma_i(A-B) \quad \text{for $1\leq i\leq n-k$}.
$$
For the spectral norm, it is sufficient to take $i=1$. For the Frobenius norm, this gives
$$
\|A-B\|_F^2\geq\sum_{i=1}^{n-k}\sigma_i^2(A-B)\geq\sum_{i=k+1}^n\sigma_i^2(A)
$$
with the equality attained, again, by $B=A_k$.
left singular vectors is by definition a unit vector $v_i$ such that :
$$
Av_i=s_i w_i \qquad A^tw_i=s_i v_i
$$
then :
$$
AA^tw_i=s_i A v_i= s_i^2 w_i
$$
so $s_i^2$ are the eigenvalues of the hermitian matrix $AA^t$ with corresponding eigenvectors $w_i$ so $w_i$ will be orthonormal, in fact it suffices to show that $w_i$ are orthogonal, let $s_i\neq s_j$ :
$$
s_i^2\langle w_i , w_j \rangle =\langle s_i^2 w_i , w_j \rangle = \langle AA^tw_i , w_j \rangle=\langle w_i , AA^tw_j \rangle=\langle w_i ,s_j^2 ww_j \rangle=s_j^2\langle w_i , w_j \rangle
$$
so $\langle w_i , w_j\rangle =0$ this implies that
$$
\langle Av_i , Av_j\rangle=\langle s_i w_i , s_jw_j\rangle=s_i s_j\langle w_i , w_j\rangle=0
$$
for the second question of rank we will use some simple fact about rank, which you can see them here :
$$
rank(Ab)\leq \min(rank(A),rank(B))\\
rank(A+B)\leq rank(A)+rank(B)
$$
so we know that the matrix $v_iv_i^t$ is of rank one (because $(v_iv_i^t)x=\langle v_i , x \rangle v_i$ forall $x$) and then for all $i$ the matrix $Av_i v_i^t$ is of rank one (if we assume surly that $A\neq 0$), so
$$
rank(A_k)=rank(\sum_{i=1}^k A v_i v_i^t ) \leq \sum_{i=1}^k rank(A v_i v_i^t)=k
$$
to verify the equality we can use this question (because the answer of the question remain true for $n\times d$ matrix) and to see that
$$
Ran(Av_iv_i^t)=\mathbb{R}(Av_i)\\
Ran((Av_iv_i^t)^t)=Ran(v_iv_i^t A^t )=\mathbb{R} v_i
$$
(because $Ran(v_i v_i^t)=\mathbb{R} v_i $)
so for $i\neq j$ :
$$
Ran(Av_iv_i^t)\cap Ran(Av_jv_j^t)= \mathbb{R}(Av_i) \cap \mathbb{R}(Av_j)=\{0\} \;\textrm{Orthogonality from the first question }\\
Ran((Av_iv_i^t)^t)\cap Ran((Av_jv_j^t)^t)=\mathbb{R} v_i \cap \mathbb{R} v_j =\{0\} \; \textrm{Orthogonality with the same argument }
$$
so $Rank(A_k)=k$.
Best Answer
Choose bases in both $\mathcal{N}(B)$ and $\mathcal{R}(V_{k+1})$. Take the vectors from both bases, that's going to be $n+1$ vectors. So that system cannot be linearly independent. Hopefully, you can show that there're non-zero vectors in $\mathcal{N}(B) \cap \mathcal{R}(V_{k+1})$ from that.
$Ax = U \Sigma V^* x$. But multiplying a vector by $V^* = V^{-1}$ is the same as representing it in the basis formed by the columns of $V$. $x \in \mathcal{R}(V_{k+1})$ and therefore its coordinates after the $k+1$ would be $0$. So the coordinates of the vector $V^* x$ are $v_1^* x, v_2^* x, \ldots, v_{k+1}^* x, 0, \ldots, 0$. After multiplication by $\Sigma$ the coordinates would become $\sigma_1 v_1^* x, \sigma_2 v_2^* x, \ldots, \sigma_{k+1} v_{k+1}^* x, 0, \ldots, 0$. Then we multiply be $U$, but it's unitary and doesn't change the norm.
We've already shown that the coordinates of $V^* x$ are $v_1^* x, v_2^* x, \ldots, v_{k+1}^* x, 0, \ldots, 0$. So the norm of that vector is $\sum_{i=1}^{k+1} |v_i^* x|^2$. But $V$ is unitary, and so is $V^*$, so after applying it to the vector of norm 1, you would get a vector of norm 1 again.