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.
head[a_] :> head[a_]withhead[a_] :> With[{b = a}, head[b_]]? $\endgroup$