Part of an answer to this question involves developing a good research plan--something that guides you in your work to extend your family tree by locating the parents of an ancestor early of New England.
The work to develop and implement a plan starts out fairly general. With time, it becomes more and more focused on precise collections/precise information. Think of it as a process of reverse engineering an "answer." So, after "Who were the parents of XXXX (XXX - XXX) m. XXX on XXX at XXXX," you are asking, "How would I go about finding clues about where XXX was born or who her early family (parents, brothers and sister, aunts and uncles) might have been?
"About places." The plan should call for a reasonable amount of study about the historical area or town(s) where your ancestor was known to have lived and died. Modern places generally evolved, they may have at one time been part of a colony, another state, a different county. Possibly they were extracted from or merged into some other identifiable "place."
As part of the work to understand the historical place(s), you will likely learn a little about the people who settled there; their motivations for settlement.
Because individuals and families migrated, you'll likely work from a timeline and learn the history of more than one area/place.
About record circumstance/collections. Once you understand a little about the place, you want to learn about the related extant historical record collections. The record circumstance varies by location and timeframe. (Not all records ever existed for all places and all times; records that once existed may have been lost to fire or flood, etc., or, "just lost.")
The FamilySearch Catalog is one place to look for lists of records about a place. Also Cyndi's list, Linpendium, etc. The US GenWeb sites can be very helpful.
Part of the work to learn the information that is available for a given town/time, etc. often involves contacting a local library, genealogical/historical society. Organizations such as these may even be repositories for local history archives (including vertical files, even family files).
It is time consuming and sometimes expensive to conduct research in these various collections. You'll start to ask familiar questions like, "Where are those records housed?"... Has the collection been indexed?" and "Is the finding aid [or are the records] online?"
Researching in the records. This is the good stuff--deed books and indexes, wills, court records, church membership rosters, voting and tax lists, militia and military records/pensions, town and vital records, published biographical sketches ...
Based on what you know "about the collection" and the kind of information the records contain, you can prioritize the work/develop a plan by which you will "exhaust" your research in those records.
About the local surnames/families/groups. As you conduct work about and in these different records, you will identify traces of early Paine/Payne and related families who settled there. What you find are may be just nubs--indexed names and maybe dates. You'll want to keep track of which nubs came from which records, because the records provide clues that you'll use to extend the research even further. I maintain research logs, but others recommend creating personas.
As you continue the work, your "collection" of research notes/logs/personas/file copies, etc. will become more and more valuable to you. You'll acquire records that contain conflicting clues/information. You may find that the research you conduct to resolve a conflict is the most valuable work you do.
Follow the children/research at the family group level. Often more information is available for events in more recent time periods. This means that although the record of Phoebe's death might not report where she was born, the marriage or death records of her children might have have asked for that information about HER. Biographical sketches written about the children (or the families into which they married) might contain family tradition or other clues that are helpful ...
> followed by text hereto add in the information from the link, that way it's quoted and highlighted separately from your question. Good luck! :)