My first two claims hold for both symmetric and public key encryption.
In the concrete security context, if there exists any secure
encryption scheme, then "Can C efficiently decrypt?" is $\mathsf{coNP}$-hard.
Proof:
For a secure encryption scheme ($\hspace{.03 in}gen$ and) $E$ and $D$, given a boolean circuit $\mathcal{C}$ such that we want to decide whether or not $\mathcal{C}$ is always true, (use the same $gen$ and have) the algorithm $F\hspace{.03 in}?D$ discard the leading bit and then apply $D$, and have $F\hspace{.03 in}?E$ output $\:\:"\hspace{-0.06 in}1\hspace{-0.06 in}" || \hspace{.06 in} E(\hspace{.04 in}pk\hspace{.02 in},m) \:\:$ except when
[$\operatorname{len}(m)$ is the number of inputs to $\mathcal{C}$ and $\mathcal{C}(m)$ is false], in which case have it output $\:\: "\hspace{-0.06 in}0\hspace{-0.06 in}" || \hspace{.06 in} m \;\;$.
(Additionally, test some arbitrary input to the circuit $\mathcal{C}$, in case $\mathcal{C}$ is always false.)
For that matter, "Does this encryption scheme decrypt correctly?" is also coNP-hard.
(Under no assumptions.)
Proof:
Given a boolean circuit $\mathcal{C}$, (let $gen$ uniformly sample an $n$ bit key,) let $\: E(k,m) = m \:$ for all $m\hspace{.02 in}$,
let $\: D(k,m) = m \:$ except when [$\operatorname{len}(m)$ is the number of inputs to $\mathcal{C}$ and $\mathcal{C}(m)$ is false],
in which case let $D(k,m)$ be anything other than $m$.
Assume AS0 and AS1 are publicly known axiomatic systems
that allow efficient testing of alleged proofs in them.
% will be shorthand for "an encryption scheme and a proof in AS0
that decryption works correctly and a proof of security in AS1".
AS1 would presumably take a cryptographic assumption as an axiom,
since otherwise Alice/Bob knowing % would be quite a feat.
One could use a standard zero-knowledge protocol to verify that Alice/Bob knows %,
although that would reveal an upper bound on the lengths
of the algorithm descriptions and the lengths of the proofs.
(This option can give a proof, while the next two options can only give arguments.)
If Alice/Bob knows %, then one could verify that they know an encryption scheme
for which they "quasi-know" (and in particular, there exists) the rest of %,
although that would reveal an upper bound on the lengths of the algorithms.
If Alice/Bob knows %, then one could verify that they "quasi-know" %,
without revealing anything else.