Q: Safe way to put a pattern on the right hand side of a rule I'm interested in creating a function or rule that generates its own set of rules. For instance, it would take as an input the expression h[m, n] and the indices m and n, and output the rule:
h[m_, n_] :> h[m, n]

What I have is:
makeLHSReplacementRule[expr_, {m_,n_}] := 
  ((expr /. m -> head[m] /. n -> head[n]) /. head[a_] :> head[a_]) /. head[A_] :> A

replacementRule[expr_, {m_, n_}] := makeLHSReplacementRule[expr, {m, n}] :> expr  

replacementRule[h[m, n], {m, n}]

The output is actually exactly what I want, which is:
h[m_, n_] :> h[m, n]

But I get an error message complaining about my having the pattern a_ appearing on the right hand side of a rule. This is making me think it might not be safe to do this (it is also very annoying, as I need to run this function many times). Does anyone know a way around this?

A: RuleDelayed::rhs is not an error message but rather a warning message.  This is an important distinction.  If you know what you are doing the message can be safely ignored.  This is also the case with Pattern::patv.(1)(2)
I would say that your method as written is not safe however for a different reason: it evaluates the Symbols m and n which means your code breaks if these are defined.  Please consider this as an alternative:
SetAttributes[replacementRule, HoldAll]

replacementRule[expr_, {var__Symbol}] :=
 (Unevaluated[expr] /.
    Thread[Thread @ HoldPattern @ {var} -> Thread @ Pattern[{var}, _]]) :> expr

Test:
m := Print["fail!"];

replacementRule[h[m, n], {m, n}]


h[m_, n_] :> h[m, n]


Or instead using Block to guard against evaluation:
ClearAll[replacementRule]

SetAttributes[replacementRule, HoldAll]

replacementRule[expr_, var : {__Symbol}] :=
  Block[var,
    Unevaluated[expr] /. Thread[var -> (Pattern[#, _] & /@ var)]
  ] :> expr


Further thoughts
Both examples above manage to avoid RuleDelayed::rhs by not having an explicit var_ in the body of the definition, but that should not be taken to mean that this is actually superior to methods that do trigger the warning.  
Here is a third approach that is more similar to your original method:
ClearAll[replacementRule]
Attributes[replacementRule] = {HoldAll};

replacementRule[expr_, {var__Symbol}] :=
  (Unevaluated[expr] /. x : HoldPattern[Alternatives[var]] :> x_) :> expr

This is somewhat more streamlined than my first method with repeated use of Thread but it throws a warning message when used:
replacementRule[h[m, n], {m, n}]


RuleDelayed::rhs: Pattern x\$_ appears on the right-hand side of rule x\$:HoldPattern[m|n]:>x\$_. >>
h[m_, n_] :> h[m, n]


(The appearance of x$ comes from the automatic renaming that takes place in nested scoping constructs of which RuleDelayed is one, despite its not being specifically advertised as such.  I started an answer which Leonid Shifrin greatly expanded regarding this that you should eventually read.)
It would in my opinion be entirely acceptable to suppress that warning with Quiet:
ClearAll[replacementRule]
Attributes[replacementRule] = {HoldAll};

replacementRule[expr_, {var__Symbol}] := 
  Quiet[
    Unevaluated[expr] /. x : HoldPattern[Alternatives[var]] :> x_, 
    RuleDelayed::rhs
  ] :> expr

In retrospect I think I prefer this to my earlier recommendation.
