I just realized that the answer
to my question is (as suspected) NO. 
Namely, in [this](http://www.sciencedirect.com/science/article/pii/030439758290113X) 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 <i>constant</i>
depending only on $\epsilon$. This is much larger than the "desired" upper bound
$c_k(G)\leq e(G)/k$. Actually, 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).
<p>
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. 
<p>
This example also shows the optimality of depth-reductions
for DAGs proved by  [Erd&#337;s, Graham and Szemer&#233;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:
<blockquote>
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$.
</blockquote>


  [1]: http://www.thi.informatik.uni-frankfurt.de/~jukna/georg.jpg