If you are doing the trip @ Misool, then you'll want to do the northern sector anyways. Waisai-Waigeo has some very nice diving. Both Kri and Sorido have no day diving on Saturdays because of their religious background (Adventist if I remember correctly). No night dive on Friday too. I believe Sorido's diving is run by a South African couple who are members on WP, Leon and Claudia.
I've never stayed at Paradise but know the area. They have some nice muck dives in the area, which is a nice change from the wall/reef drift diving in the area. This book, Diving Raja Ampat (Empat) by Burt Jones and Maureen Shimlock, is probably the best guide to where you choose to stay.
If I may suggest, instead of looking for a resort, check if any of the liveaboards are going to be around and jump on for a few days as they go up or around. Diving in a resort allows you to hit the good sites again and again, but a liveaboard is the only way to explore R4 properly.