Zero-Knowledge proof for data being decryptable to a given hash preimage
There has been some recent progress [1] on efficient zero-knowledge for such statements. Essentially they present a $\Sigma$-protocol to prove statements over general circuits. To prove the AND relation you state, you could essentially just build one large circuit which takes (the bits of) $r$ as input and outputs $h_r$ and $h_m$ so that $h_r = \operatorname{SHA256}(r)$ and $h_m = \operatorname{SHA256}(\operatorname{Dec}(\hat m, r))$, where $\hat m$ is hardcoded in the circuit.

The proofs above are of linear size in the number of AND gates in the circuit. If you want something more compact you might want to have a look at SNARKs. 

References

[1] https://eprint.iacr.org/2016/163.pdf