How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem?

Question

Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set $S$ of size $k$, if there exists another set that covers strictly more elements than $S$ does. Is this problem still NP-complete?

To be clearer, let's think about the Set Cover problem as an optimization problem: what is the maximum number of elements that can be covered by $k$ sets. The decision version is: are there $k$ sets that cover at least $m$ elements? (where $m$ is part of the input, and the version you were saying is simply the special case when $m=n$). Now the problem is, for $k$ given sets (as part of the input), does there exist $k$ other sets that cover strictly more elements than the $k$ given sets do.