スレッド履歴

まず最初に、ここはPC版のwikiなので、Switch版のデータは扱っていません。
正確な情報が欲しい場合は、公式wikiの該当ページを翻訳サイト等で翻訳して確認してください。

Paladinのページを翻訳した限りでは「Planteraを倒した後のダンジョンに出現する」
「Dungeon Brick Wallで作られたDungeonエリアに最も多くスポーンする」とのことなので、確認してみてください。
Brick wall系で出現する青いモンスター（Blue Armored BonesとNecromancer）が頻繁に登場しているかで判断可能です。
一応1/7の確率で背景と異なるモンスターも出現するらしいのですが、Paladin自体がレアなので運次第ですね。

Brick Wall系の背景壁がDungeonエリア内に無い場合は…
例えばBlue Brickｘ4(GreenやPinkでも可)で「Blue Brick Wall」をクラフトしてShimmerに投入、
「 Cursed Blue Brick Wall」を作ってDungeonにいっぱい設置すれば出現しやすくなるかも知れません。

あとは気長にやれるなら新しいワールドを用意して、そちらで（Plantera討伐まで進めて）探すのも1つの手です。
ボスを倒す戦力と召喚アイテムがあるなら、最短ルートでやればボス6体討伐で到達できます。