Believe it or not, those pot sizes are just fine for the orchids you got. With orchids, you're not supposed to look at the size of the leaves to judge whether or not the orchids need to be potted up or down - you gotta take a look at how big the root system is and pot up or down according to the size of the root system. If you removed the moss from the roots and took a look at how large, (or rather, I should say in your case, how small), the root system is you would agree with me on this one.
Plus, many Paphs tend to grow roots rather slowly. It could take several years for your orchid's roots to catch up to the leaves on the plant.
I also probably wouldn't be using moss as a potting medium for Paphs. Many Paphs, (such as those in the subgenera Brachypetalum and Parvisepalum, for example), actually grow in areas with high amounts of calcium and magnesium because many of them are found growing within a thin layer of organic topsoil on limestone cliffs or hills, which means that they grow in areas where the pH of the substrate is actually more alkaline than acidic and most likely in the pH range of 7.0 - 8.4.
The pH of Sphagnum moss can get as low as 3.0. Imo, in the long run, this will not be so good for the roots of your Paphs. Just my
.