I'm expanding my comment to an answer.
You can always do it the brute force way.
Find some permutation matrix $P_\pi$ such that none of the entries $A[i,\pi(i)]$ are $0$.
Subtract $(\min_i A[i,\pi(i)])\, P_\pi$ from $A$.
Repeat steps (1) and (2) until you're left with the $0$ matrix.
As the OP comments, to prove that it terminates, you can note that each time you are left with a multiple of a double stochastic matrix, and step (2) always adds at least one more zero entry.
We still need to show that step (1) is always possible. This follows from Hall's marriage theorem. This theorem states that such a permutation $\pi$ exists unless there is a set $R$ of rows and a set $C$ of columns such that $|R|+|C| < n$ and $A[i,j] = 0$ unless $i \in R$ or $j \in C$. In other words, all the non-zero entries are either in a row in $C$ or a column in $R$.
We will show by contradiction that such a matrix cannot be doubly stochastic. Look at the the sum of all elements $A[i,j]$ with $i \in R$ and $j \in \bar{C}$. Since each of the column sums is $1$,
$$\sum_{i\in R, j\in \bar{C}} A[i,j] = \sum_{j\in \bar{C}} A[i,j] = |\bar{C}|.$$ Also, each of the row sums is $1$, so
$$\sum_{i\in R, j\in \bar{C}} A[i,j] \leq \sum_{i\in R} A[i,j] = |R|.$$
But $|R| < |\bar{C}|$, so
$$\sum_{i\in R, j\in \bar{C}} A[i,j]\leq |R| < |\bar{C}|= \sum_{i\in R, j\in \bar{C}} A[i,j],$$
a contradiction.
Note that this gives a proof of Birkhoff's theorem. To turn it into a real algorithm, you still need an algorithm for step (1) that finds a permutation in Hall's marriage theorem. There are lots of algorithms to do this; I don't know which is the simplest one. (It's a special case of the bipartite maximum matching problem, which in turn is a special case of the assignment problem, so any bipartite maximum matching algorithm, or any algorithm solving the assignment problem, will work.).
If we can find a permutation $\sigma$ such that $A_{i,\sigma(i)} \neq 0$, for every $1 \leq i \leq n$, then we are done, because the associated permutation matrix will satisfy what you want.
So we consider the following bipartite graph $G$ on $X \sqcup Y$, $X = Y = \{1,\ldots,n\}$, and we set $i \sim j$ if and only if $A_{i,j} \neq 0$. Any perfect matching on $G$ will give us the desired permutation, so lets check that we can satisfy Hall's condition in this graph.
Let $I \subseteq X$, and we have that $N(I) = \{j : \exists i \in I, i \sim j \}$. First notice that for any $i$ by definition of $A$ and construction of $G$ we have that $$\sum_{i \sim j}A_{i,j} = m$$ So we have the following
$$\begin{align}
|I| &= \frac{1}{m} \sum_{i \in I} \sum_{j \in N(I)} A_{i,j}\\
&= \frac{1}{m} \sum_{j \in N(I)} \sum_{i \in I} A_{i,j} \quad \text{(We switched sumation order)} \\
&\leq \frac{1}{m} \sum_{j \in N(I)} \sum_{i \in X} A_{i,j} \quad \text{(We sum over all $X$, which is $m$)}\\
&= \frac{1}{m}m|N(I)| = |N(I)|
\end{align}$$
Which is exactly Hall's condition, so $G$ has a perfect matching which gives us the permutation as we wanted.
Best Answer
You can use induction on $k$. The base case $k=1$ is clear. If $k>1$, then by Birkhoff's theorem you cited (or by Hall's marriage lemma), there is some permutation matrix $P$ so that $P_{ij}>0$ implies $A_{ij}>0$ (any $P$ that is part of the Birkhoff decomposition of $A/k$ will do.) For this $P$, the $n \times n$ matrix $A-P$ has non-negative integer entries, and the sum of each column and row of $A-P$ is equal to $k-1$.By the inductive hypothesis, $A-P$ can be written as a sum of $k-1$ permutation matrices, whence $A$ can be written as a sum of $k$ permutation matrices.