What's a good algorithm for deleting multiple elements in a heap?
I think you're optimizing for the wrong metrics.  The total running time will be $\Theta(n)$ no matter what you do.  Scanning the entire array to identify which elements to remove will take $\Theta(n)$ time, so your total running time can't be any better than $\Theta(n)$.  Conversely, there is a simple algorithm that achieves $\Theta(n)$ time.  MakeHeap can be done in $\Theta(n)$ time, so it gives you a simple $\Theta(n)$ running time algorithm: scan the entire array, delete whatever you want to delete, then run MakeHeap.

However, if you're trying to optimize the amount of work per deletion and for some reason the time taken to scan the array "doesn't count" (I don't understand why it wouldn't count, but let's just run with it):

In this case there is an alternative algorithm.  Deleting a single element from a heap can be done in $O(\lg n)$ time.  So, if you want to delete $k$ items, delete each one-by-one.  Total running time: $\Theta(n)$ to scan the array, $\Theta(k \lg n)$ to delete them.