And if someone wants to say "The left-handed man" would it be correct to say "Ο αριστερόχειρας άντρας" ?
It would need to specify the left thing. So ο άνδρας στο αριστερό σπίτι=The man on the left house.
The English phrase "the lefthand man" should be acceptable. Lefthand means 'on the left' (as opposed to left-handed).
But that does seem slightly strange English. The man on the left or the left hand side one/man would be more usual, I think. Agree?
Sorry, no. But this may be a difference of usage in different places. 'the left hand side man' would read to me as the as the man belonging to the 'left hand side' of a team, for example.