Q: Do tefillin need to be painted with a certain type of black paint?
A: According to halakhah, there is actually no need for the tefillin themselves to be painted black at all. The requirement to be black is for the straps only (cf. Rambam, Hilkhot Tefillin 3:1,13), and even then only the outer surface (cf. ibid).
The halakhah at 3:14 actually concludes by saying: “And it is an ornamentation to the tefillin that they are black, their case and the entire strap [i.e. the front and the back].” This is also the opinion of the Tur and the Shulhan Arukh.
[See also Arokh HaShulhan, Hilkhot Tefillin, Siman 32:5 for a discussion of the opinions regarding the blackness of the batim and the straps.]
I assume that what ever is “kosher” for the straps is “kosher” for the tefillin themselves. I say “kosher” in quotes because there is no discussion in the Mishneh Torah or Hazal about what specific material is necessary for a proper blackening either. All of this discussion comes from latter-day authorities and usually stems from concerns based on the “kabbalah.”
So, le-aniyut da’ati, it would seem that according to all opinions it is enough to use something derived from either kosher or synthetic sources, and the blackening should be done by a Jew.