The answer to both of your questions is yes. As suggested by the edit, consider the graph $G(A)$ whose vertex set is the set of non-zero entries of $A$, and where two entries are adjacent if they are in the same row or column. Now, if $G(A)$ contains a perfect matching then $A$ is is the support of an even sign configuration (see the last paragraph of the question). On the other hand, if $A$ is the support of an even sign configuration, then it is easy to construct a perfect matching in $G(A)$.

Thus $A$ is the support of an even sign configuration if and only if $G(A)$ has a perfect matching.

Now, by Edmond's Blossom Algorithm, the problem of finding a perfect matching in an arbitrary graph (not just maximum degree 4) is in P. So both of your problems can be solved in polynomial-time.

The answer to both of your questions is yes.

As suggested by the edit, consider the graph $G(A)$ whose vertex set is the set of non-zero entries of $A$, and where two entries are adjacent if they are in the same row or column. Now, as mentioned in the latest edit, if $G(A)$ contains a perfect matching then $A$ is the support of an even sign configuration. On the other hand, if $A$ is the support of an even sign configuration, then it is easy to construct a perfect matching in $G(A)$.

Thus $A$ is the support of an even sign configuration if and only if $G(A)$ has a perfect matching.

Now, by Edmond's Blossom Algorithm, the problem of finding a perfect matching in an arbitrary graph (not just maximum degree 4) is in P. So both of your problems can be solved in polynomial-time.