I don' t like this guy, he kind of creeps me out in subtle ways. But that and "is it OK to compliment people" are two different questions; for things like clothes, hairstyle and so on I think it's incoherent for it not to be OK. Thing is, if it's something that a person deliberately does to their appearance, that's, you know, appearance to other people. How do you then turn around and say it's inappropriate for people to comment? And most people are happy about it--your efforts to look good are recognized.
There may be particular situations and especially particular people you don't want to hear it from, but I think it's a bad idea to make that into a general "Nobody gets to be nice lest it be offensive" rule. And I don't think gender is generally an issue about this; I've been pleased when either men, women or whatever complimented my hat and my look, and I've complimented women on their scarves and men on their ties and it's all good.