I think the answer is that trivially when there is an automorphism all properties of the vertex, including $P$, are carried over to its image. Then, other properties like (strong) regularity may play a role. I was also thinking of studying the distance matrices of these graphs to see if they have something in common...

That's bad news. I was guided by the path graph, for which $P_i=P_{n-i+1}$, and of course this is consistent with the action of the path-reversing $\sigma$. Also, $P$ is constant over the symmetric cycle graph, and for every non-central vertex of the wheel or star graphs. However I saw that it fails for Frucht graphs, which are $3-$regular but asymmetric, and yet $P$ is constant. Could it actually just be a sufficient, but not necessary condition?

I'm thinking of a more general version of the problem. Right now we have found a necessary condition for $P_i=P_j$, but I have reasons to conjecture that $P_i=P_j$ if and only if there exists $\sigma\in\text{Aut}(G)$ such that $\sigma(v_i)=v_j$ (which of course implies the two vertices have the same degree). I'm open to ideas for a proof... but of course not a complete answer!

Thank you very much, Chris. Your answer is pretty close to what I was building up to: the big difference is that I was trying to calculate directly $(L-E_j)^k$ (I got stuck there and even asked another question here). I missed the idea of taking the time derivative! [I am an undergraduate physicist doing some research in quantum computation theory, the problem comes from there :)]

@ChrisGodsil You are not wrong, I edited the post. I believe the more familiar English term for coordination number is degree of a vertex, so I changed that as well.