You could create a helper function:

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"}

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"}