Remark 1. The eigenvalues of $A\otimes B +B\otimes A +cI$ are not the $\alpha_i\beta_j+\beta_i\alpha_j+c$ except when (for example) $AB=BA$.
Remark 2. The complexity of your problem is not in $O(p^6)$. Indeed, there are special methods to solve equations in the form $AXB+CXD=E$ where $A,C\in M_{m,m},B,D\in M_{n,n},E\in M_{m,n}$ are known and $X\in M_{m,n}$ is unknown. cf.
i) http://www.maths.lth.se/na/courses/NUM115/NUM115-09/sylvester.pdf
uses an algorithm that is an extension of the Bartels–Stewart method and the Hessenberg-Schur method. Originally the Bartels –Stewart algorithm was used to solve the Sylvester equation.
ii) http://www.dm.unibo.it/~simoncin/matrixeq.pdf
That is important, is that the previous algorithms have complexity $O(n^3+m^3)$ that is much smaller than the complexity of the Kronecker product method. For example, solving a Lyapounov equation ($AX+XA^T=B$ with $n\times n$ matrices) -with Bartels–Stewart- has the same complexity ($\approx 40 n^3$) as finding eigenvalues and eigenvectors of a $n\times n$ matrix.
EDIT. You can also read this paper
https://pdfs.semanticscholar.org/5c47/c67aabe615a94174c418ebc5029e5630567d.pdf