How to prove correct decryption in Paillier cryptosystem
This can be done by using a zero-knowledge proof to prove that a Paillier ciphertext is an encryption of zero. Specifically, let $c$ be the original ciphertext, and let $m$ be the decryption that Alice sends back to Bob. Then, both Alice and Bob can each locally use the homomorphic property to compute a ciphertext $c'$ that is an encryption of the value encrypted in $c$ minus $m$. Note that if $c$ is an encryption of $m$, then $c'$ is an encryption of zero.

Thus, all that is needed is for Alice to prove in zero-knowledge that $c'$ is an encryption of zero (equivalently, that $c'$ is a $n^2$'d power). This can be done very efficiently, using the method described in Section 5.2 of A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting by Damgard and Jurik.

In light of a comment in a different answer, it is possible for the prover to compute the randomness given the public key, if it doesn't have it. Specifically, let $c=r^N \bmod N^2$ (this is an encryption of zero). Then, compute $M= N^{-1} \bmod \phi(N)$ and $r = c^M \bmod N$. This works since $c^M = r^{N\cdot M} = r^{1+k\cdot \phi(N)}  = r \bmod N$.