On May 5th, 1818, Karl Marx, hero of the international proletatiat, was born. His revolution of Socialist theory reverberates throughout the world carries on to this day, in increasing magnitude. Every passing day, he is vindicated. His analysis of Capitalism, development of the theory of Scientific Socialism, and advancements on dialectics to become Dialectical Materialism, have all played a key role in the past century, and have remained ever-more relevant throughout.
He didn't always rock his famous beard, when he was younger he was clean shaven!

Some significant works:
Economic & Philosophic Manuscripts of 1844
The Eighteenth Brumaire of Louis Bonaparte
The Civil War in France
Wage Labor & Capital
Wages, Price, and Profit
Critique of the Gotha Programme
Manifesto of the Communist Party (along with Engels)
The Poverty of Philosophy
And, of course, Capital Vol I-III
Interested in Marxism-Leninism, but don't know where to start? Check out my "Read Theory, Darn it!" introductory reading list!
Communism is human nature. Communism existed in the Americas and Australia for thousands of years. It probably existed in the rest of the world too before agriculture, but our historical records from other regions were destroyed. By contrast, Australia has the most intact ancient histories in the world.
It's important to draw a line between Primitive Communism and Communism as a post-Socialist society. Primitive Communism is founded upon small, isolated communities, while Marx's Communism is one of large industry run along a common plan, democratically, to suit the needs of all.
What's more accurate is to say that what's considered "Human Nature" changes alongside Mode of Production. It was indeed "Human Nature" to have cooperative, communal units, but it is also "Human Nature" to produce under Capitalism, and still further "Human Nature" to move beyond the discordant production of Capitalism to a cohesive Socialist, and eventually Communist, society.
The mode of production is never human nature. Human nature is a factor, but the mode of production is something that is socially constructed and subject to material constraints, like tools and the environment in which people live.
But socializing and sharing empathy is virtually universal, and the impetus to share food or shelter or community is something that capitalist society teaches us to avoid. So one of the things we strive for through the abolition of capitalism is the restoration of human connections and care that are currently robbed from us. So I can totally see where you are coming from re: the extent to which the communism we want to build constitutes a return. But it is even more a step forward, a transformation into the future constructed from the bones of the present.
Re: what Marx called "primitive communism", which we might better call egalitarian societies based on hunting and gathering and sometimes agriculture, such societies have actually existed everywhere people have lived. You can find clear historical examples of such societies in the Americas and Australia, yes, but also in the Middle East, Ukraine, Great Britain, Ethiopia, Pakistan/India, China, etc. As you mention, any of these societies did not have written records or they were lost, but we can understand how they lived based on their homes, food, tools, dress, cohabitation, and spatial distribution of all these things.