Just a few facts:
1. "Paper", an app from developer "Contradictory", has existed in the App Store since October 27, 2011. This is presumably before miSoft registered their Paper. (https://twitter.com/FiftyThree/status/430873195097632769) Contradictory is clearly a name squatter.
2. miSoft's Paper launched ~5 months after Paper by FiftyThree. (https://twitter.com/FiftyThree/status/430845528805756928)
3. miSoft renamed another of their apps "Kid Paint" to "Paper Express" on 12/20/2012 after FiftyThree won App of the Year (https://twitter.com/georgpetschnigg/status/43091631900616704...)
I can't find it anymore, but the icon was very simple, a plain white A4 piece of paper on a blue background. I assume this app existed on the store before yours because I managed to accidentally download it on your release day.
When a name is generic like Paper I think it's okay to have multiple apps on the App Store.