I choose to write this as an answer rather than a comment because my
feeling is that all answers are rather long comments, and this is
going to be too long for a comment. No one is actually saying yes or
no to your question. I will not either (I do not know whether there is such a structure that is known
as such, but I believe that such a structure can exist, though I have
no proof for it).
To begin with, I expect you looked at the wikipedia page on cellular
automata, where your animation comes from. But you do not seem to have
drawn any other information from that page.
Your question is about order and stability of complex patterns
emerging from some chaos based on simple (?) rules. Indeed, one answer
comments that you look for complex structures that "behave in ways
that resemble the behavior of people or animals".
Emergence of order from chaos, and of (more or less) stable complex
structures immediately rings a bell in real physical systems:
thermodynamics. So my first move was to call Google with the
words: automata theory thermodynamics, and the second answer was the
wikipedia page on cellular automata.
Indeed it seem that some researchers (including Stephen Wolfram) have
investigated the issue in relation with the thermodynamics aspects
found in nature. This is not very detailed, and I guess one would have
to analyze thermodynamics of cellular automata models, whatever that
may be. This has been done to some extent with reversible cellular automata.
There is probably more to it. The wikipedia page alludes to the
creation of large stable structures (class 4 cellular automata),
"reminiscent of the phase transition in thermodynamics".
That is all I can say about this line of thought, though I believe it
should be an important one for the kind of question asked. The work on
trying to understand physics and biology from cellular automata model
is obviously also relevant.
This said, the page also mentioned the work of John von Neumann who
proved the existence of a self replicating system based on cellular
automata."This design is known as the tessellation model, and is
called a von Neumann universal constructor." Replicators were found
more recently fr Conway's game of life.
Building on this, one can imagine that some type $A$ of such
structures could have an ability to clear up space to let other
$A$ structures find space to reproduce. As you remark yourself, this
is to be expected from the Turing completeness of cellular automata.
So one can imagine that the structure you suggest could exists. Which probably means that infinitely many different such structures could exist.
However your question is whether it could emerge spontaneously, if one
waits long enough. But you do not specify an initial state.
Given an "infinite" cellular universe, and a random initial
configuration, I do not see why not, at least for some types of
celluler automata. It may take some 13 billion years though (just a
randomly chosen duration). But maybe the most interesting pointer in
that direction is the class 4 cellular automata of Wolfram
classification. See also this reference.