I imagine the best bet for becoming "legal" would be to reach out to some sort of church/organization dedicated to helping the homeless or other refugees. /they would likely be more sympathetic and understanding to the "I lost everything at some undisclosed point in the past" explanation than a government employee. There are a few avenues you can take with this:

 - The organization accepts them as a refugee or whatever and provides for them while they assists them in establishing some kind of legitimacy. Your protagonist that is from this plane of existence volunteers to put them up at their house and "sponsor" them. As long as they aren't trying to get a credit card or anything major you can sort of ignore it from then on. Even minor encounters with police can be explained by this. Most local police would be familiar with organizations such as this and might accept the explanation "Oh you're one of those Our Lady of Plot Convenience fellas" and write them off.

 - Introduce an ancillary character at such an organization that is especially helpful. Maybe they think the off worlder/alien/(?) is handsome/beautiful or interesting and uses their contacts at the local government ID providing office, since this is the sort of thing they do for work, to expedite the ID procuring process. This is sort of a hand wave as there are official procedures and requirements and what not but it's a story and have all the minutia of obtaining a new ID down to a T isn't high on the list of priorities.

 - Hand wave it away the same way they did on 'Sleepy Hollow'. Ichabod Crane comes back from the past and befriends a present day police officer. They explain him as a visiting professor from England. He is granted legitimacy via hanging out with a cop. Whenever they get in a pickle she flashes her badge and says "He's with me." The same can be done for any transdimensional character, have the protagonists uncle/brother/father/sister/mother/good friend be some kind of police officer or other official or other respected public figure and use the "I'm with him" excuse. This should work for most interesting story telling situations. No one reads a story about a time traveling wizard form another dimension to watch them fill out loan applications.