We treat four cases:

I. $x, y \ge 0$

$\sqrt{4^x + 5^y}$ is rational if and only if $4^x + 5^y$ is a perfect square, i.e., there exists $n \in \mathbb{N}$ such that $4^x + 5^y = n^2$. Analyzing this equation modulo $3$, we have $4^x \equiv 1 \pmod{3}$, $5^y \equiv (-1)^y \pmod{3}$, and $n^2 \equiv 0, 1 \pmod{3}$, hence $y$ needs to be odd. Let $z \in \mathbb{N}$ be such that $y = 2z + 1$. The previous equation becomes $4^x + 5 \cdot 25^z = n^2$.

If $x \ge 2$, then $4^x \equiv 0 \pmod{8}$, $5 \cdot 25^z \equiv 5 \pmod{8}$, while $n^2 \equiv 0, 1, 4 \pmod{8}$, which means the equation has no solutions in this case. We are left with the cases when $x = 0$ and $x = 1$.

For $x = 0$ we have $4^x + 5^y \equiv 2 \pmod{4}$, hence $4^x + 5^y$ cannot be a perfect square.

If $x = 1$, then $5^y = (n-2)(n+2)$, hence there exist $a, b \in \mathbb{N}$, with $a + b = y$, such that $n-2 = 5^a$ and $n+2 = 5^b$. By subtraction, $5^b - 5^a = 4$. If $a, b \ge 1$ then $5 \mid 5^b - 5^a$, hence $5 \mid 4$, contradiction. As $a < b$, it follows that $a = 0$, then $b = 1$, i.e., $y = 1$. We obtain the solution $x = y = 1$.

II. $x, y < 0$

Let $u = -x, v = -y, u, v > 0$. $\sqrt{4^x + 5^y}$ is rational if and only if there exist $p, q \in \mathbb{N}^*$, coprime, such that $4^x + 5^y = \frac{p^2}{q^2}$, i.e., $\frac{4^u + 5^v}{4^u \cdot 5^v} = \frac{p^2}{q^2}$, which means $p^2 \cdot 4^u \cdot 5^v = q^2(4^u + 5^v)$. Numbers $4^u \cdot 5^v$ and $4^u + 5^v$ are coprime, therefore every prime factor of $4^u + 5^v$ is a prime factor of $p^2$, which means that it appears at an even exponent. It follows that $4^u + 5^v$ is a perfect square, and, similarly, $4^u \cdot 5^v$ is a perfect square. From case I it follows that $4^u + 5^v$ is a perfect square if and only if $u = v = 1$, but then $4^u \cdot 5^v = 20$ is not a perfect square. We conclude that there are no solutions in this case.

III. $x < 0, y \ge 0$

Let $u = -x \in \mathbb{N}^*$. Then $\sqrt{4^x + 5^y} = \frac{\sqrt{1 + 4^u \cdot 5^y}}{2^u}$ is rational if and only if $1 + 4^u \cdot 5^y$ is a perfect square, i.e., there exists $n \in \mathbb{N}$ such that $1 + 4^u \cdot 5^y = n^2$. Then $4^u \cdot 5^y = (n-1)(n+1)$. As $u > 0$, $n$ is odd and $(n-1, n+1) = 2$. We distinguish the following sub-cases:

A. $n-1 = 2 \cdot 5^y$, $n+1 = 2^{2u-1}$

B. $n-1 = 2$, $n+1 = 2^{2u-1} \cdot 5^y$

C. $n-1 = 2^{2u-1}$, $n+1 = 2 \cdot 5^y$

D. $n-1 = 2^{2u-1} \cdot 5^y$, $n+1 = 2$

In sub-case A we obtain $2^{2u-2} - 5^y = 1$, i.e., $(2^{u-1} - 1)(2^{u-1} + 1) = 5^y$. It follows that $2^{u-1} - 1$ and $2^{u-1} + 1$ should be powers of $5$, but no two powers of $5$ are at distance $2$.

Sub-case B leads to $n = 3$ and, immediately, to $4 = 2^{2u-1} \cdot 5^y$, with no solutions.

In sub-case C we get $5^y - 2^{2u-2} = 1$. Then $5^y \equiv (-1)^y \pmod{3}$ and $2^{2u-2} = 4^{u-1} \equiv 1 \pmod{3}$, therefore $y$ needs to be odd. It follows that $5^y \equiv 5 \pmod{8}$, hence $2^{2u-2} \equiv 4 \pmod{8}$, i.e., $u = 2$. We obtain the solution $x = -2, y = 1$.

Sub-case D leads to $n = 1$ and then to $0 = 2^{2u-1} \cdot 5^y$, with no solutions.

IV. $x \ge 0, y < 0$

Let $v = -y \in \mathbb{N}^*$. Then $\sqrt{4^x + 5^y} = \sqrt{\frac{1 + 4^x \cdot 5^v}{5^v}}$ is rational if and only if there exist $p, q \in \mathbb{N}^*$ coprime such that $\frac{1 + 4^x \cdot 5^v}{5^v} = \frac{p^2}{q^2}$, i.e., such that $p^2 \cdot 5^v = q^2(1 + 4^x \cdot 5^v)$. Numbers $1 + 4^x \cdot 5^v$ and $5^v$ are coprime, hence, as in case I, they need to be perfect squares. We have seen in the previous case that $1 + 4^x \cdot 5^v$ is a perfect square only when $x = 2$ and $v = 1$, but in this situation $5^v = 5$ is not a perfect square. We conclude that in this case there are no solutions.

To summarize, the only solutions to the problem are $x = y = 1$ and $x = -2$, $y = 1$.