The question is very general and so the following is only a partial solution. My main motivation was to draw the connection between this and k-hitting sets.
As Arindam has pointed out, this problem (or the decision version thereof) could be used to solve the subgraph isomorphism problem: "Is $H$ a subgraph of $G$ if any $0$ edges of $G$ are removed?". But as is often the case, we still want to know "is it possible to do better than the naive solution?"
The naive solution:
for i in 0 ... (|E(G)|-|E(H)|+1)
for every i-subset of edges, S, in E(G)
if H is not a subgraph of (G - S)
return k=i-1 as the greatest number of edges that can be removed
Ignoring the obvious edge cases (returning $-1$ when $H$ is not a subgraph of $G$) then the cost is basically $\sum_{i=0}^k \binom{|E(G)|}{i}$ computations of he subgraph isomorphism problem on inputs (basically) $G$ and $H$. And so, we are basically up against a possibly exponential number of subgraph isomorphism problems.
The problem can be restated as a hitting set problem (also known as a vertex cover of a hypergraph problem). Let $S$ be the set of all sets, $T$, where $T$ is a set of $|E(H)|$ edges of $G$, and $H$ is isomorphic to $G - (E(G) - T)$.
Note, $S$ is not every mapping of $H$ onto $G$, but is every edge set that can be mapped to.
Let $h$ be the size of the minimum hitting set of $S$. Then $k=h-1$.
This is neat, but it is not immediately useful. Calculating a minimum hitting set is NP-hard, and the input into the problem is possibly exponential in the size of the input of our original problem. Double-wam-o.
However, it does provide us with a case for a fast approximation. If $|E(H)|$ is small (and by that I mean bounded by some constant $e_H$), then we have $|S| = O(\binom{|E(G)|}{e_H})$. Also, an $e_H$-approximation can be computed in polynomial time. Thus the real work is in finding $S$, which can be done with $\binom{E(G)}{e_H}$ cases of the graph isomorphism problem. The naive solution does not compute in polynomial time when $E(H)$ is bound because $k$ is not bound.