Different ROMs need different GApps?
It depends on the actual android version of the ROM you flashed. it the ParanoidROM and Cyanogenmod ROM are both Android 4.2 then you don't need a new set of gapps, if there aren't then if might just be safe to get a new set of gapps