Can this be done?
In general, there is a way: you can prove the statement you sketch using zero-knowledge proofs. Due to [1] we know that zero-knowledge proofs for any language in NP exist. Let us write down what you want to prove as an NP language $L$. Therefore let $\sf (sk, pk)$ be the key pair, consisting of a secret key $\sf sk$ and a public key $\sf pk$, and let $\sf pk'$ be the public encryption key (corresponding to some secret decryption key $\sf sk'$) used to encrypt $\sf sk$ so that $C = {\sf Enc}({\sf pk'}, {\sf sk};~\rho)$, i.e., the ciphertext $C$ contains an encryption of $\sf sk$ under public encryption key $\sf pk'$ and $\rho$ denotes the randomness used upon encryption. In addition we may assume without loss of generality that there exists an efficient algorithm $\sf VKey$ which takes as input a key pair $\sf (sk, pk)$, and outputs $1$ whenever $\sf sk$ is the key corresponding to $\sf pk$ and $0$ otherwise. Now we can write down $L$ as follows:
$$
L = \{ ({\sf pk'}, C, {\sf pk}) ~|~ \exists~({\sf sk}, \rho) : {\sf VKey}({\sf sk},{\sf pk}) = 1 ~\land~ C = {\sf Enc}({\sf pk'}, {\sf sk};~\rho)\},
$$
Clearly, if we know $({\sf sk}, \rho)$ corresponding to a tuple $({\sf pk'}, C, {\sf pk})$ we can efficiently verify membership in $L$. Therefore $L$ is indeed an NP language.
Efficient instantiations?
Regarding efficient instantiations one needs to be careful, as the most efficient approach no longer allows to obtain $\sf sk$ upon decryption but only $\sf pk$. In particular, assume that we have some group $\mathbb{G}$ of prime order $p$ generated by $g$ where we assume the decisional Diffie-Hellman assumption to hold. Now assume we use some scheme where the $\sf sk$ is a random element in $\mathbb{Z}_p$ and the corresponding public key is its "image" in the group with respect to $g$, i.e., ${\sf pk} = g^{\sf sk}$. Additionally assume that we choose to use exponential ElGamal in $\mathbb{G}$ as encryption scheme, (i.e., ${\sf Enc}({\sf pk}', {\sf sk}) := (g^r, {\sf pk}'^r \cdot g^{\sf sk})$ for some uniformly random $r$ in $\mathbb{Z}_p)$. Now, one may observe that we can no longer efficiently obtain $\sf sk$ upon decryption but only $\sf pk$. However, if your use case does not require to be able to recover $\sf sk$ upon decryption the aformentioned instantiation is very efficient: one can make use of $\Sigma$-protocols (see, e.g., [2]).
If your use case also requires to be able to efficiently recover $\sf sk$ upon decryption, you will require more costly zero knowledge proofs: for example encrypting a bit-wise representation of the key and proving the statement with respect to this bit-wise representation of the key, or to use Paillier as an encryption scheme, which however may require zero-knowledge proofs over groups of different orders (see e.g., [3]).
Instantiations using a symmetric encryption scheme?
In case you want to use a symmetric encryption scheme things will get a lot more expensive as this would require to prove statements over general circuits and also to somehow make the link to the algebraic setting where the keypair $({\sf sk}, {\sf pk})$ lives in. You could have a look at this paper [4] to find out more about how this could be instantiated.
Also note that, in contrast to asymmetric encryption schemes, symmetric encryption schemes are typically not binding. Thus such an instantiation will require some additional measures to ensure that the encryption key you use to prove the statement is indeed the key it should be.
Bottomline
I think that using an asymmetric encryption scheme will be preferable in practice - if your use case allows it at all. Even if one might have to do ZK proofs over groups of different orders this will be much more efficient and much simpler to implement compared to using a symmetric encryption scheme.
References
[1] http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf
[2] http://www.cs.au.dk/~ivan/Sigma.pdf
[3] https://pdfs.semanticscholar.org/ad71/f5dcef871bdfaad01be9da6d378b010b36d4.pdf
[4] https://eprint.iacr.org/2016/583.pdf
