Hi, I hope you'll pause to thank T. Kerwin for adding MUCH essential information with the forum - as always, his work is impressive!
Do follow his example and post transcriptions of records, rather than writing a narrative or posting informal, unsourced notes (which in this case are rather jumbled and confusing). The transcriptions tell the story.
Andrew Peter Paulsen was born in the Schleswig-Holstein area that lies between Denmark and Germany, per the census records transcribed by T. Kerwin. Andrew may have been born in the former duchy of Schleswig in modern Denmark in Tønder, Sønderborg, Aabenraa, or Haderslev amt - OR - more likely - he was born just south of there, in the former duchy of Holstein that is now in Germany but was ruled by Denmark when Andrew was born.
Andrew is likely Anders in his birth record. His name Peter may have been spelled Peder. If he was named according to traditional naming patterns, his father is named Paul something. Andrew is "son of Paul."
I found an Anders who could well be "yours," but need more information.