Translation:Can you give me a piece of paper?
I don't think the 可以 is referring to 我 ("I") in this sentence. The 可以 applies to the 你 ("you"), which is implied but not explicitly included. This sentence is asking if the addressee can give the speaker (我) a piece of paper (hence the inclusion of the verb 给). I'm assuming "May I have a piece of paper" would be translated as 我可以有一张纸吗？.
Not really incorrect, but 對不起 is used when you did something bad and apologize. We seldom say 對不起 when you ask someone for something. 抱歉 or 不好意思 are both better here, like "excuse me".
Well, I'm Taiwanese, so I'm not familiar to Chinese using. They always think we speak too soft, like women whereas we think they speak too rude.