Each error message like that has a corresponding "name" that you can put into a messages.properties file, and they can also be internationalized with message_en.properties or messages_fr.properties.
I just forget the exact "name" to use it is something along the lines of
javax.jsf.required=My New {0} Message
I know they are on the internet and on my laptop, I actually have a bookmark on a page that has them all, but I am not on my laptop, so I am sorry I cannot give that link, but you can find it through a Google search.
Good Luck, and I hope at least I showed you were to look and what to look for.