How to replace numbers in a string?

You could create a helper function (the point of the helper function is to avoid calling FromDigits twice):

incString[s_] := With[{r = FromDigits[s]},
    If[EvenQ[r],
        IntegerString[r+2, 10, StringLength[s]],
        s
    ]
]

and then use this helper function in StringReplace:

StringReplace[
    string,
    i:DigitCharacter..~~".png" :> incString[i]<>".png"
]

{"E:\job\a\000251.png", "E:\job\a\000254.png", \ "E:\job\a\000253.png", "E:\job\a\000256.png", "E:\job\a\000255.png", \ "E:\job\a\000258.png"}

StringReplace[string, 
 a : NumberString ~~ "." /; EvenQ[FromDigits[a]] :> 
   StringPadLeft[IntegerString[FromDigits[a] + 2], StringLength@a, "0"] ~~ "."] 

{"E:\job\a\000251.png",
"E:\job\a\000254.png",
"E:\job\a\000253.png",
"E:\job\a\000256.png",
"E:\job\a\000255.png",
"E:\job\a\000258.png"}

Borrowing the three-argument IntegerString idea from Carl's answer with an alternative replacement rule:

StringReplace[string, a : NumberString ~~ "." :> With[{b = FromDigits @ a}, 
   IntegerString[b + 2 (1 - Mod[b, 2]), 10, StringLength @ a]] ~~ "."]

same result

It seams that there has not been an answer involved with RegularExpression yet, which is quite efficient when dealing with patterns of strings.

StringReplace[string, x : RegularExpression["\\d*[02468]\\."] :> ToString[NumberForm[ToExpression[x] + 2, 5, NumberPadding -> "0"]]]

{"E:\\job\\a\\000251.png",
 "E:\\job\\a\\000254.png",
 "E:\\job\\a\\000253.png",
 "E:\\job\\a\\000256.png",
 "E:\\job\\a\\000255.png", 
 "E:\\job\\a\\000258.png"}

---

Update

As @yode pointed out in the comment, IntegerString is better here on the right-hand side of :>.