The easiest way to convert to a religion is to capture a province of said religion from a neighboring opponent. Once this is done, you have to make religious zealots appear so that they convert half of your provinces. You can do so by sending a missionary to try to convert this new province, but drop the missionary funding to 0 ducats. The goal here is to raise the unrest (+6 from the missionary) for as long as it takes to make the zealots appear without really converting the province to your current state religion.
Once the zealots are there, and have control of your province, they will move on from province to province, converting each one of them the second they have won the siege. Once they have control of 50% of your provinces, you can accept their demands, which will change your state religion to the desired religion.
All that remains for you is to convert your other provinces.
I have not personally tested if they can automatically move to provinces overseas (in your case I would assume the nearest catholic province will be in the new world, unless France, Spain or Portugal have colonies somewhere in Malaysia and or Australia), but other types of rebel can "teleport" to remote provinces, so I assume religious zealots can too. If you are not neighboring any catholic countries, you have to find a way to do so, else it will be impossible to convert your country to the teachings of Cathol.