You aren't allowed to ask for paper work anyway. Here is all they are allowed to ask: "A public entity may ask if the animal is required because of a disability and what work or task the animal has been trained to perform." See section f at https://www.law.cornell.edu/cfr/text/28/35.136

That said, just asking people with apparently inappropriate dogs what task the animal has been trained to perform would be a first step towards removing fake service animals. If they can't answer, I assume there is something you can do, but I don't know what that is exactly. It may depend on your state.

In the case of a specifically badly behaving fake (or even real) service animals, section b of the same document says: "A public entity may ask an individual with a disability to remove a service animal from the premises if - (1) The animal is out of control and the animal's handler does not take effective action to control it; or (2) The animal is not housebroken.", so a dog barking or pooping in a business can definitely be ordered removed.