Hi Anya, as a teacher on italki I get this too. It's a fine line to walk, trying to define how people should contact you without coming across as unfriendly.
If it's a case of the other person asking me to go on Skype to help them with their English (read: hand them a free lesson), I usually reply with a positive message telling them that they're more than welcome to look at my teacher profile and book a session. That's normally enough of a hint. If the other person doesn't (want to) understand - and thankfully, this doesn't happen often - then I have no problem deleting their message. It's never come to the point where I'd need to block someone, but that's still a possibility.
I don't see any problem with you telling the other person that you only give your Skype out to paying students. Or, you could just delete the message without answering it. Your teacher profile shows that you provide paid lessons, so it's a bit out of line for someone else to decide you ought to provide the same service to them for free, isn't it?
Of course, it's a different matter with real language exchanges or members who I've got to know well. :)
PS. I think Spagnola's advice is good, as it does limit the people who could randomly message you. There's still the "Contact Teacher" button on your profile, if legitimate students want to contact you.