How can I modify a package from the Mac App Store?
It depends upon the app. For example, I've been able to replace the icon of djay (bought it in the MAS) with the one from Cyberduck, and djay launches just fine (except it's got a rubber duck as its icon now :-))
If the developer does an integrity check at start time, you're out of luck.