Perfect Matching with ``set-over-like" constraints?
The problem can be solved in $O(n^k \, \text{poly}(n))$ time, so it's not "NP-hard in $n$" unless P=NP.

Here's one simple algorithm.  Enumerate all subsets $E'$ of $E$ such that $|E'|\le k$.  Check whether the union of labels of $E'$ is equal to $\{1,2,\dots,k\}$; if not, move on to the next candidate for $E'$.  Then, check whether there's a perfect matching of $G$ that includes all edges of $E'$.  This can be done as follows: check that no pair of edges in $E'$ meets in a common vertex; let $V^*$ be the set of vertices that don't touch any edge of $E'$, and $E^*$ the set of edges both of whose endpoints are in $V^*$; then check whether $G^*=(V^*,E^*)$ has a perfect matching.  If such a perfect matching exists, you have found a valid solution to your original problem.  There are $O(n^k)$ possible subsets $E'$, so the entire procedure runs in $O(n^k \, \text{poly}(n))$ time.  Correctness follows because if there is a set of edges whose labels have union equal to $\{1,2,\dots,k\}$, then there is a set of size $\le k$ with this property.