My old passport and new passport were stapled together while returning from the visa embassy. After I managed to remove the staples from my Passport. Now I can see staple holes on the back cover of my new passport. Would it be a problem for my travel? Should I apply for a new passport?
No, it's not a problem. Staple holes, stickers etc on the back of your passport are very common and are ignored by immigration officials, because the back cover holds no useful information and has no use other than protection.
Staple holes on the front cover of your passport could be a problem if they affect the biometric data on the other side (name, birth date, etc), but this doesn't sound like it's the case here.