Hi Michelle.
The completion editor is designed to allow you to edit completion records of users who are (or were previously) assigned. It doesn't allow you to make any changes to whether or not users are assigned. So this feature isn't going to help you remove the user from the program.
The 'Invalid - Select a valid status' option is telling you that you need to select one of the other statuses. It's there so that when displaying a program or certification which is invalid (some data doesn't make sense, such as if the database record contained 'status' 'in progress' and 'time completed' has some date in it, which should never happen), when you go to edit that record it will initially show 'Invalid - Select a valid status' and you will have to choose another status before you can save the record.
In regards to the audience, do you mean that it is a "Set" audience, as opposed to a "Dynamic" audience? If so, then the end date has no effect - check the help popup next to the "End date" when editing an audience. You can just remove the user from the audience and this will (when cron runs) unassign the user from the program. If you mean that "you set the audience in the assignments tab" and that it is actually a "Dynamic" audience, then the user won't automatically be removed from the audience, after the "End date", even if they no longer meet the conditions for inclusion. In this case, you'll need to remove the end date, allow the dynamic audience to update, then put the end date back. But be aware that this will update the audience for all related users.
Program messages can't be triggered manually. You've got two options. You could use the Administration -> Users -> Bulk actions page to send a message to the users you select. Alternatively, you could remove and re-add the users to the program. This would cause them to be sent an unenroled message (if it is set up) and the enrolment message. This will only work in Totara 2.9.13 or 9.1 or above, due to patch TL-7752.
Nathan