To a reasonable approximation the protons and neutrons in a nucleus occupy nuclear orbitals in the same way that electrons occupy atomic orbitals. This description of the nucleus is known as the shell model. The exclusion principle applies to all fermions, including protons and neutrons, so the protons and neutrons pair up two per orbital, just as electrons do. Note that the protons and neutrons have their own separate sets of orbitals.
I say to a reasonable approximation because neither nuclear orbitals nor atomic orbitals really exist. The atomic orbitals we all know and love, the $1s$, $2s$, etc, appear in an approximation known as the mean field. However the electron-electron pair repulsion mixes up the atomic orbitals so strictly speaking they don't exist as individual separate orbitals. This effect is small enough to be ignored (mostly) in atoms, but in nuclei the nucleons are so close that the nuclear orbitals are heavily mixed. That means we have to accept that the shell model may be a good qualitative description, but we have to be cautious about pushing it further than that.
You are correct that the standard explanation of "filling up single-electron orbitals" is confusing. That's because it makes two key simplifying assumptions which are rarely stated explicitly:
First, it neglects the Coulomb interaction between the elections, so that the Hamiltonian can be decomposed as
$$H_\text{full} = \sum_{i=1}^n H^{(1)}_i,$$ where $H^{(1)}$ represents a single-electron Hamiltonian (e.g. the hydrogen atom Hamiltonian). In this very special case, it can be shown that the eigenfunctions can all be represented as Slater determinants of single-electron eigenfunctions, so that we really can meaningfully talk about the wave functions of the individual electrons without having to measure all of them at once. In the general entangled case where we fully incorporate the Coulomb interaction, we can't do this, and the "orbital" picture breaks down, and as you say, the physical consequences of the Pauli exclusion principle become very hard to intuit.
In practice, we very often use a hybrid approach called the "Hartree-Fock" approximation (which works surprisingly well and is ubiquitous in quantum chemistry). It's a variational approximation in which we try to minimize the energy of the exact interacting Hamiltonian, but only over the space of Slater determinants of single-particle wavefunctions. In this case it turns out that the best energies come from giving different electrons effective hydrogen-like orbitals, but with different effective nuclear charges that are less than the true nuclear charge $Ze$. Physically, this represents the fact that the interelectron repulsion is being approximately incorporated into a "screening" effect that the inner electrons have on the outer ones, by partially cancelling out the nuclear charge. (Moreover, the best effective nuclear charge turns out to depend on the angular momentum quantum number $l$ (although not on $m$). This breaks the energy degeneracy between orbitals with different values of $l$ that one finds in the hydrogen atom.) But it is inherently just an approximation; in the exact ground-state wave function, you can't talk about individual electron wave functions.
Within the HF approximation, we can assume that each electron has a well-defined orbital, but any arbitrary set of orbitals (that respects Pauli exclusion) is a valid eigenstate. Why do we always assume that they get filled up from lowest to highest energy? Because of the second implicit assumption, which is that the electrons are in thermal equilibrium at zero temperature, so that they are in the ground state of the full multi-electron Hamiltonian. This is an excellent approximation: except in exotic high-temperature systems like plasmas, the electrons are almost always found to be in their ground state. (This is lucky, because it turns out that for the exact exited states, the Hartree-Fock approximation works much less well than for the exact ground state.)
Best Answer
I'll try to give a qualitative view. There are an array of forces working together at various distances and strengths that stabilize bulk matter. The Pauli Principle could probably be considered to be one of the lowest fundamental levels.
The Pauli Exclusion Principle is often confused with the cause of macroscopic effects like being responsible for atoms or molecules not occupying the same space, but that is not really the full picture. Atoms and molecules after all are mostly empty space. The exclusion principle is only partly responsible for why macroscopic scale matter can't be in the same place at the same time.
And the stability of electrons themselves in an atom are unrelated to the Pauli Exclusion Principle which is strictly about quantum states of fermion matter. In this respect fermion matter must occupy some finite volume. The electrons of each atom cannot all fall into the lowest-energy orbital and must occupy successively larger shells cannot be squeezed too closely together.
Andrew Lenard considered the balance of attractive (electron–nuclear) and repulsive (electron–electron and nuclear–nuclear) forces and showed that ordinary matter would collapse and occupy a much smaller volume without the Pauli principle. But this doesn't mean you can't compress bulk matter with millions of atoms and molecules tighter together you just have to overcome the other repellent forces first. While the Pauli Principle sets the ultimate limits on all the bits that are fermions.