We recently accepted an App and after further feedback from members determined he would not be a good fit.

How do we change the Applications Status frpom Approved to Rejected and send a new notification?

This is not currently an option. But you do have the email address in the app itself, so you could at least toss an email at the applicant directly.