I just realized that the answer to my question is (as suspected) NO. Namely, in this paper, Georg Schnitger constructed a directed acyclic graph $G$ with $n$ vertices, and $e(G)\approx n\log n$ edges such that, for every $0\leq \epsilon < 1$ and $k=n^{\epsilon}$, we have that $c_k(G)\geq \alpha\cdot e(G)$, where $\alpha=\alpha(\epsilon)$ is a constant depending only on $\epsilon$. This is much larger than the "desired" upper bound $c_k(G)\leq e(G)/k$. Actually, I think that using the Kraft inequality, one can show that $c_k(G)=\Omega(n\log(n/k))$ holds for every $k$: show that at least $m\log m$ edges must be removed in order to disconnect any given subset of $m$ leaves, and use the argument of the proof above (haven't verified the details yet).
The graph $G$ is constructed as follows. ![alt text][1] Take a complete binary tree of depth $t$; hence, we have $n=2^{t+1}-1$ vertices. Remove all edges. Connect each vertex with all leaves, which were previously its descendants. Direct the new edges in the following way: the vertex receives edges from his left leaves and sends edges to his right leaves.
This example also shows the optimality of depth-reductions for DAGs proved by [Erdős, Graham and Szemerédi](http://www.renyi.hu/~p_erdos/1976-26.pdf), and generalized by [Valiant](http://link.springer.com/chapter/10.1007%2F3-540-08353-7_135?LI=true) to the following important fact:
In a DAG with $m$ edges and depth (maximum length of a path) $d$, it is enough to take out $mr/\log d$ edges to reduce the depth to $d/2^r$.