To me, what's unclear how much this is a work issue (interfering with his job performance) and how much it's just an "I personally don't like it" thing. The question and comments from the OP sort of say some things about this:
... I am ashamed of the image we produce as a company when he looks like that.
My boss agrees that the guy looks bad, and that it would be better if something was done about it.
But since we are consultants, we have values. As to signals from clients - no, and I don't think we will get any since it's not very common in Germany to express that sort of things.
It's clear that the OP believes that this is bad for work, but the bulk of the specifics are tied to people's personal opinions of whether he looks good.
So it seems very difficult to tell whether a work-related approach (e.g. telling him it may be affecting his work, possibly going through boss or HR) is a great idea or a horrible idea, and I would be reluctant to try to answer or judge the merits of the answers that have been posted.
Bottom line, I think that this question could be either "how do I tell someone that I don't like their appearance?" or "how do I tell someone that their appearance is interfering with their work?" and those two have fairly different answers.
There's a fair bit of evidence that this is an issue:
Very directly in a comment from one of the close voters:
[...] I'm having a difficult time separating your personal complaints with Bob from your objective ones, and am voting to close until you clean this up.
Some question about the "personally ashamed" versus "issue with clients"
Does your company have an official dress-code? And does I am ashamed of the image we produce as a company when he looks like that imply it's just you, or are you getting signals from the clients as well? Who hired Bob, and how did he look at that time?
and finally, several answers which address the possibility of the personal issue variant, as well as several non-close-voting commenters picking up on it.