Homelessness is a protected class in some jurisdictions.
Rhode Island and Illinois, for instance, have each adopted a "Homeless Bill of Rights" establishing the following guarantees:
(1) the ability to use and move freely in public spaces, including public sidewalks, parks, transportation, and buildings, among other spaces;
(2) equal treatment by state and municipal government agencies;
(3) freedom from discrimination while maintaining employment;
(4) emergency medical care;
(5) ability to vote, register to vote, and receive documentation necessary for voting;
(6) protection from disclosure of his or her personal records and confidential information; and
(7) a reasonable expectation of privacy over personal property to the same extent as one would have in a permanent residence.
Connecticut and Puerto Rico also provide some level of protection for the homeless. To the best of my knowledge, no such protections are in place in either New Jersey or New York City.
Exactly how far these laws go in protecting a homeless person's right to enter a store or restaurant will vary by jurisdiction.
For more about this topic, see the Yale Law Journal article, "Ban the Address: Combating Employment Discrimination Against the Homeless."