Cases with Alternatives failed

The issues with your code

There are two different issues here. First is that indeed, HoldPattern would prevent Alternatives@@... to evaluate. This is why

Cases[rules, HoldPattern[Alternatives @@ targets -> _]]

will not work. However, when you use

Cases[rules, HoldPattern[Evaluate[Alternatives @@ targets]] -> _]

you run into another issue: Cases has an extended syntax Cases[expr, lhs_->rhs_,...], where it interprets Rule as a part of its extended syntax, rather than a part of expression to be matched. Conceptually, the correct solution here would be, for example, to use Verbatim to escape Rule:

Cases[rules,Verbatim[Rule][HoldPattern[Evaluate[Alternatives @@ targets]], _]]

(* {a -> 1, b -> 2} *)

HoldPattern and Verbatim

However, I have to note that the whole business with HoldPattern here seems either unnecessary or insufficient. If you don't worry about possible evaluation of a, b, etc, then you don't need HoldPattern:

Cases[rules, Verbatim[Rule][Alternatives @@ targets, _]]

(* {a -> 1, b -> 2} *)

So, it looks like a classic case of misuse of HoldPattern, where you use HoldPattern where Verbatim should be used.

OTOH, if you do worry about evaluations of a, b, etc, then you need to do a whole lot more to prevent their evaluation, than just in the line with Cases. But this doesn't seem to be the case you are interested in.

HoldPattern has attribute HoldAll

Attributes[HoldPattern]
(* {HoldAll, Protected} *)

So one can use the following injection

Cases[rules, HoldPattern[Alternatives@## -> _] & @@ targets]
(* {a -> 1, b -> 2} *)

P.S. Conceptually, HoldPattern is here the wrong tool for the job, even if this works. See Leonid's answer.

This should probably be a comment (and maybe I have missed it):

This does not address the issue re: Alternatives but note FilterRules does this.

rules = {a -> 1, b -> 2, c -> 3};
FilterRules[rules, {a, b}]

or

rules = {a -> 1, b -> 2, c -> 3, d -> 4}
FilterRules[rules, {d, a, b}]

yields: {a -> 1, b -> 2, d -> 4}