Consider the connectivity interdiction problem, which can be solved in polynomial time [1].
Connectivity(Unweighted) Connectivity interdiction
Given a graph $G$ and integer $k$. Find a set $R$ of $k$ edges, such that the min-cut in $G-R$ is minimized.
Your problem is the same as this problem because $R$ is the $k$ discounted edges in the minimum $k$-discounted cut.
Zenklusen's paper discusses a more general weighted version of the problem. Each edge has a weight (independent from cost). $R$ is chosen so the weight is at most $k$. That problem admits a PTAS. The special case we care about is when the weights are all $1$, which is the case solvable in polynomial time.
- Zenklusen, Rico, Connectivity interdiction, ZBL06945298..