Re: Patenting your software/app...
Patent Law is different depending on the country so make sure to research yours. Maybe someone on the forum is/was a patent attorney that can give detailed advice? I am not but I have had experience in patenting and selling my own patents over 30+ years. Here is the most relevant advice ... do you have the resources (expertise, time, money) to protect your patent? If not, then don't even get started. It's that simple. Formally copyright it, yes, absolutely. Copyright and Patent are two completely different things.
As far as having someone having your app removed from a store ... I'd imagine there are a vast array of things that can make that happen beyond someone claiming that it was theirs first.