Catholics are not a majority, only the major Christian denomination by a small margin with 24% vs 22% Protestants. By far the biggest group with 46,2% are the non-religious. And the denominational affiliation hasn’t to be determined by people checking boxes, your denomination is part of every German’s personal file, because if you do belong to a denomination you have to pay church tax, and the Finanzamt (our IRS) wants to know. Leaving a religion and getting exempt from church tax is an administrative act you have to personal visit your town hall for, and it even costs a fee. So statistics about religious affiliation in Germany are very precise.
What’s even more important: Only 5% of the population regularly visit religious services, so many who are officially and administratively religious are only so on paper.
Catholics are only a majority among Christians in Germany, and in the last years their membership declined fast, even faster than that of the Protestants.
UPDATE 2: This morning I went to privately owned small scale Mail and parcel place. Explained all my woes. They did not understand why i was denied twice. Very pleasantly suprised with the service, great people. It’s being sent via DHL
DHL is a German company, so this confirms that the country of Germany doesn’t have a mail policy of prohibiting the shipping of religious items. Seems like the OP’s case was a misunderstanding by a USPS employee of a restriction only applied by the USPS anyway.