Select certain number of column elements of a stochastic matrix, maximum one element per row
Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.