"his statement" refers to the statement made by the man, namely, "I am lying." His statement does not include the initial "a man walks up to you and says," as he did not say that.
He is saying it with the intention to create a paradox, not with the intention to insincerely deceive
How do you know what his intentions are? What if he is insane, believes he is telling the truth, and insincerely tries to deceive you? Then it would be a true statement.
There is enough information given to either prove that no matter what the man's intentions, the statement itself
must be true, or that no matter what the man's intentions, the statement itself
must be false. I suppose that could be a big hint