For your first question, it's not hard to show with a back-and-forth argument that for any uncountable cardinal $\kappa$, the structure $\left<\kappa; \in\right>$ has $\left<\omega^\omega; \in\right>$ as an elementary substructure. This implies that $p$ cannot be first-order definable in $\left<\kappa; \in\right>$ (with $\kappa$ uncountable), since there exists $\alpha < \kappa$ such that for any $\beta,\gamma < \alpha$, $p(\beta,\gamma) < \alpha$, but by the argument given here, an ordinal has this property if and only if it is multiplicatively indecomposable, and $\omega^\omega$ is the first (infinite) multiplicatively indecomposable ordinal.

For your second question, I have a partial answer that probably can be leveraged into a full answer. Itay Neeman has a paper Monadic Definability of Ordinals which deals with some questions related to what is definable in monadic second order logic in $\left<\mathrm{On}; <\right>$. In it he shows that $\alpha + \beta$ and $\alpha \cdot \beta$ are not definable with $\alpha$ and $\beta$ with parameters (although oddly enough, the set of definable ordinals *is* closed under those operations). Assume that for arbitrarily large cardinals $\kappa$, there is a formula $\varphi(x,y,z)$ such that $\left<\kappa;\mathcal{P}(\kappa);\in\right> \models \varphi(\alpha,\beta,\gamma)$ if and only if $p(\alpha,\beta)=\gamma$. Then by the class pigeonhole principle, there is a single formula $\varphi(x,y,z)$ which works for arbitrarily large $\kappa$.

Now I claim that this would imply that $p$ is definable in $\left<\mathrm{On};<\right>$ in monadic second order logic. Specifically, we have that $p(\alpha,\beta)=\gamma$ if and only if there exists an ordinal $\delta > \max\{\alpha,\beta,\gamma\}$ such that in $\left< \delta; \mathcal{P}(\delta); \in\right>$ the formula $\varphi(x,y,z)$ defines a function $q: \delta^2 \to \delta$ such that

- $q(x,y) < q(z,w)$ if and only if either $\max\{x,y\} < \max\{z,w\}$; $\max\{x,y\} = \max\{z,w\}$ and $x < z$; or $\max\{x,y\} = \max\{z,w\}$, $x=z$, and $y < w$ and
- the function $q$ is a surjection onto $\delta$.

This is enough to ensure that $q$ is the restriction of $p$ to $\delta$. Since $\varphi(x,y,z)$ works for arbitrarily large $\kappa$, we have that this formula I have described does indeed define $p$.

Now that $p$ is definable, you have enough machinery to talk about maps between ordinals and you could define $\alpha +\beta$ as the smallest ordinal $\gamma > \alpha$ that has an order preserving map from $\beta$ whose range is disjoint from $\alpha$. Since $\alpha+\beta$ isn't definable (as a function), this is a contradiction, and we have that $p$ can't be definable in $\left<\kappa;\mathcal{P};\in\right>$ for arbitrarily large $\kappa$.

This argument can be extended to include definitions with parameters. This goes for the argument for the first question as well since Gödel's pairing function has an implicit definition that can be expressed in first-order logic.

By looking at Neeman's paper more closely, you could probably extract a more direct argument that gives that $p$ isn't definable for any $\kappa$.