The question of "where you are from" is complicated for many English-speaking people because they live in North America, where there are historical and political considerations about where you are from.
I consider myself to be "from" Canada yet my paternal grandfather was born in Britain somewhere (probably Wales). I don't consider myself "from Wales". My maternal grandparents are from Quebec; their families had lived there for several generations. At what point do they stop being "from France"?
Yet I can't call myself a "Native Canadian" without confusing some people because there are other peoples, the First Nations (or Indians) who are more commonly referred to as "Native Canadians".
Given that so many people are immigrants, or relatively recently descended from immigrants, it usually takes several questions to identify people's family backgrounds. And that is maybe one of the better terms to use: Family Background. You can ask what someone's family background is and they might have a quick answer, such as "China" or "Ireland". I still don't have a good answer for that either because it's not a simple question.
Generally there is no such thing as an official "origin" for your family that would be recorded on ID cards or other official papers, thus there aren't really any good single words or set phrases to label these origins.
Finally, your suggestion of hails from only works if the person or group in question is recently from the place you're naming. You hail from the place you were born or grew up. You could describe your family as hailing from some place, but if you're trying to say that generations ago your family "hailed from" New York, you'd have to use extra words to indicate that. "My family hails from New York" would be most likely interpreted as your parents and yourself being from New York. If your parents had never lived in New York, I'd suggest you should specify that: "My family originally hailed from New York." Hails from is not a formal term.