How can machine possibly possess consciousness if computation is a human idea? Suppose a computer simulates a human brain so that it passes the Turing test. Suppose that this brain is given sensory stimuli that correspond to an experience of being in an Earth-like world.  From my understanding, proponents of computationalism suppose that this simulated brain would have qualia.

The neural network, its state, and the program code are stored on a computer, and can only be observed if someone knows how to use this computer. How a neural network is represented in memory and on disk, depends on data structures, computer architecture, endianness, et cetera.

Suppose then that the last human on Earth dies, but the simulation keeps running on the computer. If there is no one in the Universe who understands how this particular computer works, then no one would be able to observe this simulated brain.  In other words, this brain would be impossible to “decode”, and yet it would supposedly still experience qualia.

It follows that if this is the case, then nothing prevents other “invisible” brains from existing.

We know that a computer is a computational device, and it is running a complex neural network that corresponds to a human-like mind, but the Universe doesn't “know” it.  It is our interpretation of what is happening. I can't stray from the conclusion that if the premise is true, then there may be different processes that isomorphically correspond to computations, some of which may isomorphically correspond to minds, but we won't know it because we don't see this isomorphism.

Why couldn't processes inside the Sun correspond to some computation (albeit in a non-straightforward way) which corresponds to a mind? By that logic, there could be infinitely many minds, all experiencing some sorts of qualia, “encoded” in different ways in all processes in the world.

Conversely, what if we replace a computer with a man (with a large lifespan) meticulously following the algorithm on paper. Would his computations somehow give rise to consciousness within a brain simulated on paper?

This just doesn't make sense to me.
Do computationalists believe this, or do they have a counter-argument?
Introduction
Your thoughts seem to straddle panpsychism and computationalism.  It is also possible you are just raising a question about physicalism: &quot;if mental thoughts are a result of physical interactions, then why would consciousness be limited to things with brains?&quot;.  Well, the short answer is that it's fundamentally not, but neither is a fusion reaction and you don't see them popping up all over the place.  They only appear (or &quot;emerge&quot;, as it were) in specific places where the conditions are just right.  So, the physicalist presumes, does the mind.  I will also note that physicalism (a form of monism) is basically the mainstream scientific stance.
Computationalism
Note that your suggestion:

Would his computations somehow give rise to consciousness within a brain simulated on paper?

would be an extreme interpretation of computationalism.  At it's core, computationalism just says that mental states are grounded in mental representations (semantics) operating on context (syntax): they are part of the cognitive process.  Individual computationalists can interpret, to varying degree, how stringent the requirements are on the underlying hardware.
Chomskian linguistics and David Marr's theory of vision were two empirical studies that really influenced the perception of cognitive scientists in favor of computationalism in the 70's.  More recent neuroscience literature has favored the connectionist view (note the two are not necessarily mutually exclusive).
A more recent literature review of consciousness, Towards a cognitive neuroscience of consciousness: basic evidence and a workspace framework, summarizes its empirical findings:
Three fundamental empirical findings on consciousness:

Cognitive processing is possible without consciousness
Attention is a prerequisite of consciousness
Consciousness is required for specific mental operations

3. would seem to be consistent with computationalism (the union of computation and consciousness).  More support for the computationalist stance:
The free-energy principle: a unified brain theory?

Agents can suppress free energy by changing the two things it depends on: they can change sensory input by acting on the world or they can change their recognition density by changing their internal states. This distinction maps nicely onto action and perception

Connectionism:
Yet another empirical perspective comes from another physicalist view called connectionism.  Connectionism has gained popularity among neuroscientists as we develop technology to better probe brains and model neural mechanisms computationally.
Consciousness as Integrated Information: a Provisional Manifesto

(i) the quantity of consciousness corresponds to the amount of integrated information generated by a complex of elements; (ii) the quality of experience is specified by the set of informational relationships generated within that complex.

Some literature that supports Tononi's idea:
Breakdown of cortical effective connectivity during sleep.
A Theoretically Based Index of Consciousness Independent of Sensory Processing and Behavior
More support for connectionism:
The brainweb: Phase synchronization and large-scale integration

The emergence of a unified cognitive moment relies on the coordination of scattered mosaics of functionally specialized brain regions.