An example of an exists-sentence such that the sentence is true on an infinite model M, yet on every submodel, the sentence is false

As Noah and Eric pointed out, the statement of the proplem is missing the word "proper" (the sentence should be false only on the proper substructures of $M$, since $M$ is alwaays a substructure of itself). And the problem can be solved vacuously by considering a structure $M$ with no proper substructures.

The solution as you described it makes no sense. Here's an example which does have proper substructures and which I believe is similar in spirit to the intention of the proposed solution (but simpler).

Consider the language $\{P,f\}$, where $P$ is a unary relation symbol and $f$ is a unary function symbol. Let $M = \mathbb{N}$, where $P^M$ holds only of $0$ and $f^M$ is the successor function $f^M(n) = n+1$.

The substructures of $M$ are of the form $\{k,k+1,k+2,\dots\}$ for any $k$.

Consider the sentence $\exists x\, P(x)$. This sentence is true in $M$ (witnessed by $0$), but false in every proper substructure of $M$ (since no proper substructure of $M$ contains $0$).

If I understand correctly, you're looking for an infinite structure $M$ and some $\exists$-sentence true in $M$ but false in all of $M$'s proper substructures. The given solution appears a bit garbled and incomplete, and is also excessively complicated.

The simplest way to whip this up is to build an $M$ with no proper substructures whatsoever. In this case it's vacuously true that all sentences are false in all proper substructures of $M$. As Eric Wofsey commented this can trivially be done in an infinite language. For a finite language example, consider $\mathbb{N}$ with $0$ and successor.