How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem? 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.
Here is a reduction from Set Cover to your problem. Let $(\{S_1,\ldots,S_m\},k)$ be an instance of Set Cover, and let $U = S_1 \cup \cdots \cup S_m$. Let $x_1,\ldots,x_k$ be $k$ new elements, and consider the following instance of your problem:


The sets are $S_i \cup \{x_j\}$ for $i \in [m]$ and $j \in [k]$, together with the set $U$.
The given cover consists of $S_1 \cup \{x_j\}$ for $j \in [k-1]$ together with $U$.


The given cover covers all elements but $x_k$. There is a cover which covers more elements – that is, all elements – iff $U$ can be covered by at most $k$ sets from $S_1,\ldots,S_m$.