What's a good algorithm for deleting multiple elements in a heap? I have a binary min-heap, size n, and I want to delete a number of
elements, identified by some predicate.

Any algorithm needs at least n tests of the predicate (preferably,
exactly n), so the interesting performance metrics are the number of
moves of elements, and the number of additional tests of the
predicate.

One possible way is to first delete elements from the corresponding
array, using a single pass to delete elements and compact the array.
And then rebuild the heap from the array. Both steps are O(n). But as
far as I understand, the rebuild step can need n moves of elements
even if only one or two elements are deleted, if they are at unlucky
positions in the array.

I wonder if there's some good algorithm which


needs O(n) element moves in the worst case
needs few extra tests of the predicate, say total n + O(log n) tests
in the worst case
needs a lot fewer then n element moves in the special cases that
only a few elements are deleted, or only a few elements are kept.
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.