Actually, if leading zeroes are permissible, then the lowest prime is 00013. 00013 + 31000 = 31013, which is prime.
Although it may be tied with the number 13 preceded by a larger odd number of zeroes. 0000013 doesn't work, and neither does 000000013 or 00000000013 or 0000000000013, but I'll bet there is some larger odd number of zeroes that do work.
re: Some observations and two answers.
