Regular, Gorenstein and Cohen-Macaulay  All the statements below are considered over local rings, so by regular, I mean a regular local ring and so on;
It is well-known that every regular ring is Gorenstein and every Gorenstein ring is Cohen-Macaulay. There are some examples to demonstrate that the converse of the above statements do not hold. For example, $A=k[[x,y,z]]/(x^2-y^2, y^2-z^2, xy, yz, xz)$ where $k$ is a field, is Gorenstein but not regular, or $k[[x^3, x^5, x^7]]$ is C.M. but not Gorenstein. 
Now, here is my question:
I want to know where these examples have come from, I mean, have they been created by the existence of some logical translations to the Algebraic combinatorics (like Stanley did), or even algebraic geometry, or they are as they are and they are some kind of lights that have been descended from heaven to their creators by any reason!
 A: I will argue that the examples you gave are "simplest" in some strong sense, so although they look unnatural, if Martians study commutative algebra they will have to come up with them at some point. 
Let's look at the first one $A=k[[x,y,z]]/(x^2-y^2, y^2-z^2, xy,yz,zx)$. Suppose you want 

a $0$-dimensional Gorenstein ring which is not a complete intersection (complete intersections are the cheapest way to get Gorenstein but non-regular, for example $k[[x]]/(x^2)$). 

Then it would look like $A=R/I$, where $R$ is regular and $I$ is of height equals to $\dim R$. If $\dim R=1$ or $2$, then $I$ would have to be a complete intersection, no good (now, the poor Martian may not know this at the begining, but after trying for so long she will have to give up and move on to higher dimension, or prove that result for herself). Thus $\dim R=3$ at least, and we may assume $R=k[[x,y,z]]$ (let's suppose everything are complete and contains a fied).  
Since $I$ is not a complete intersection, it must have more than $3$ minimal generators. If it has $4$ then it would be an almost complete intersection, and by an amazing result by Kunz (see this answer), those are never Gorenstein.
So, in summary, a simplest $0$-dimensional Gorenstein but not complete intersection would have to be $k[[x,y,z]]/I$, where $I$ is generated by at least $5$ generators. At this point our Martian would just play with the simplest non-degenerate generators: quadrics, and got lucky! 
(You can look at this from other point of view, Macaulay inverse system or Pfaffians of alternating matrices, see Bruns-Herzog, but because of the above reasons all the simplest examples would be more or less the same, up to some linear change of variables)
On to your second example, $k[[t^3,t^5,t^7]]$. Now very reasonably, our Martian wants 

a one dimensional Cohen-Macaulay ring B that is not Gorenstein. 

Since $\dim B=1$, being a domain would automatically make it Cohen-Macaulay. The most natural way to make one dimensional domains is to use monomial curves, so $B=k[[t^{a_1},...,t^{a_n}]]$. But if $n=2$ or $n=3$ and $a_1=2$ you will run into complete intersections, so $a_1$ would have to be $3$ and $n=3$ at least, and on our Martian goes...
(Again, you can arrive at this example by looking at things like non-symmetric numerical semi-groups, but again you would end up at the same simplest thing). 
Reference: I would recommend this survey for a nice reading on Gorenstein rings. 
A: All of these conditions are very important in algebraic geometry. I don't know much about the algebraic combinatorics aspect of these notions, but my feeling is that came from geometry and not vice versa.
The reason we care about these notions is that even though it would be nice to always work with non-singular varieties (a.k.a. regular) it can't always be done. For instance, families of non-singular varieties may degenerate to singular ones and most of the time there is no way to resolve these singularities in the families. 
For instance, any families of hypersurfaces (e.g., plane curves) degenerate to singular ones. However, hypersurfaces are Gorenstein so if we can handle those we are fine. So, in particular, to give an example of a Gorenstein but not regular ring you only need to find a singular hypersurface. For example $k[[x,y]]/(x^2-y^3)$ is such an example. 
Now if you study more general varieties than hypersurfaces you might not always be able to guarantee that they degenerate to Gorenstein varieties. On the other hand, if you consider stable families, then if the general fiber is smooth, then all fibers are Cohen-Macaulay. This is a non-trivial result. You can find it here.
As Kevin mentioned, the Gorenstein and Cohen-Macaulay properties can be measured by the dualizing complex. $X$ is Cohen-Macaulay if and only if its dualizing complex is a sheaf and it is Gorenstein if and only if it is Cohen-Macaulay and its dualizing sheaf is a line bundle. I am not totally sure what he means by the last statement, but $X$ is regular if the sheaf of differentials is locally free. If it isn't regular one needs to think about what "top differentials" mean. For a discussion of that see this MO answer.
Anyway, this gives us an easy way to construct Cohen-Macaulay but not Gorenstein varieties. You "only" need a Cohen-Macaulay variety whose canonical bundle is not a line bundle.
An easy way to do that is to use the fact that rational singularities are always Cohen-Macaulay. For surface singularities you can ensure that they are rational from their resolution graph (see Artin's paper) and it is easy to cook up a resolution graph that makes sure that the canonical sheaf of the singularity is not a line bundle. 
Another way to make sure that a singularity is Cohen-Macaulay is to compute its local cohomology. See Lemma 4.1 of this paper of Patakfalvi for a condition. That tells you when a cone is Cohen-Macaulay and then just pick a variety with the right embedding and it will give you something non-Gorenstein. For instance, take a cone over $\mathbb P^1\times \mathbb P^1$ embedded by the $(2,1)$ line bundle. 
