The most straightforward way is the following:

Let $p(u,v)$ (“p” for palindrome) be a predicate which means “any path from $u$ to $v$ is a palindrome”. We are interested in $p(S, F)$ for each starting state S and each finishing state F. To compute it, we need an auxiliary predicate $c(u,v)$ (“c” for connected): “there exists a pat from state $u$ to state $v$“. $c$ can be computed in $O(n^3)$ time using transitive closure.

Let $E$ be the set of transitions. Let $ell(u,v)$ be the label (symbol) on edge $u to v$. Then:

$$p(u,v) = false, text{if $exists u’, v’: (u,u’), (v’, v) in E, c(u’,v’)=true, ell(u,u’) ne ell(v’,v)$}$$

Simply put, if there is a path $u to u’ leadsto v’ to v$ such that the first and the last symbols don’t match, $p(u,v)$ is false.

If such a path doesn’t exist, we can define $p(u,v)$ recursively:

$$p(u,v) = land_{u’, v’: (u,u’), (v’, v) in E, c(u’,v’)=true} p(u’, v’)$$

I.e. if there is a path $u to u’ leadsto v’ to v$ such that $u’ leadsto v’$ is not a palindrome, then $p(u,v)$ is not a palindrome.

Now, we can write a DFS-like solution. Let $G$ be a graph where vertices are pairs of states and edges are as defined by the second equation:

$$ (u,v) to (u’,v’) iff (u,u’), (v’, v) in E, c(u’,v’)=true $$

Intuitively, an edge leads from a problem to a “subproblem”.

Our starting vertices for DFS are $(S,F)$ for each starting state $S$ and each finishing state $F$. We need to check that none of these vertices reaches a “bad” vertex, where $(u,v)$ is bad if it fails the condition from the first equation, i.e.:

$$exists u’, v’: (u,u’), (v’, v) in E, c(u’,v’)=true, ell(u,u’) ne ell(v’,v)$$

This is a standard use-case for DFS or BFS.