Pattern Match symbols that begin with same letter?

You may use SymbolName with StringStartsQ.

{e1 x e2 y e3 z e4} /. s_Symbol /; StringStartsQ["e"]@SymbolName[s] -> 3
(* {81 x y z} *)

Hope this helps.

Improvement Courtesy of Karsten. 7 (see comments)

Just a way using Pick:

var = {e1 , x , e2, y, e3, z, e4};
Pick[var, StringTake[#, 1] & /@ (ToString /@ var), "e"]

Improved:

Pick[var, StringTake[ToString /@ var, 1], "e"]

Using Cases

Cases[var, _?(StringTake[ToString[#], 1] == "e" &)]

Using StringMatchQ (method is corrected by Alexey Popkov, see comments):

Pick[var, StringMatchQ[ToString[#], "e" ~~ ___] & /@ var]

Improved:

Pick[var, StringMatchQ[ToString /@ var, "e" ~~ ___]]

MatchQ[e3, a_ /; First[Characters[ToString[a]]] === "e"]