Let $G$ be a graph and $A$ its adjacency matrix. Is it correct to say:
$$\text{Aut}(G)=\{PAP^T:P\text{ is a permutation matrix}\}$$
I believe so, but I have never seen it written this way.
If so, then there must be permutation matrices $P_1,P_2$ with $P_1\ne P_2$ and an adjacency matrix of a graph such that $P_1AP_1^T=P_2AP_2^T$ for otherwise $\text{Aut}(G)=S_n$.
For example if $G$ is a cycle on $4$ vertices say $1-2-3-4-1$. Its automorphism group is $D_4$. What would be an example of $P_1,P_2$ in that case?
No. The set you've given is the set of all adjacency matrices that describe graphs isomorphic to $G$. The set you're looking for is the set of all isomorphisms (so permutations rather than graphs) that map the graph to itself.
What you should have instead is something like $$ \text{Aut}(G)=\{P: PAP^T = A \text{ and } P\text{ is a permutation matrix}\} $$
For your example: take $G= C_4$, with matrix $$ A = \pmatrix{ 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0 } $$ Consider $$ P_1 = \pmatrix { 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0 }, \quad P_2 = \pmatrix{ 0&1&0&0\\ 1&0&0&0\\ 0&0&1&0\\ 0&0&0&1 } $$ $P_1 \in \text{Aut}(G)$ since $P_1AP_1^T = A$. However, $$ P_2AP_2^T = \pmatrix{ 0&1&1&0\\ 1&0&0&1\\ 1&0&0&1\\ 0&1&1&0 } \neq A $$ So, $P_2 \notin \text{Aut}(G)$