GMM uses overlapping hills that stretch to infinity (but practically only count for 3 sigma). Each point gets all the hills' probability scores. Also, the hills are "egg-shaped" [okay, they're symmetric ellipses] and, using the full covariance matrix, may be tilted.
K-means hard-assigns a point to a single cluster, so the scores of the other cluster centers get ignored (are implicitly reset to zero/don't care). The hills are spherical soap bubbles. Where two soap bubbles touch, the boundary between them becomes a flat (hyper-)plane. Just as when you blow a foam of many soap bubbles, the bubbles on the inside are not flat but are boxy, so the boundaries between many (hyper-)spheres actually forms a Voronoi partition of the space. In 2D, this tends to look vaguely like hexagonal close-packing, think a bee-hive (although of course Voronoi cells are not guaranteed to be hexagons). A K-means hill is round and does not get tilted, so it has less representation power; but it is much faster to compute, especially in the higher dimensions.
Because K-means uses the Euclidean distance metric, it assumes that the dimensions are comparable and of equal weight. So if dimension X has units of miles per hour, varying from 0 to 80, and dimension Y has units of pounds, varying from 0 to 400, and you're fitting circles in this XY space, then one dimension (and its spread) is going to be more powerful than the other dimension and will overshadow the results. This is why it's customary to normalize the data when taking K-means.
Both GMM and K-means model the data by fitting best approximations to what's given. GMM fits tilted eggs, and K-means fits untilted spheres. But the underlying data could be shaped like anything, it could be a spiral or a Picasso painting, and each algorithm would still run, and take its best shot. Whether the resulting model looks anything like the actual data depends on the underlying physical process generating the data. (For instance, time-delay measurements are one-sided; is a Gaussian a good fit? Maybe.)
However, both GMM and K-means implicitly assume data axes/domains coming from the field of real numbers $R^n$. This matters based on what kind of data axis/domain you are trying to cluster. Ordered integer counts map nicely onto reals. Ordered symbols, such as colors in a spectrum, not so nicely. Binary symbols, ehn. Unordered symbols do not map onto reals at all (unless you're using creative new mathematics since 2000).
Thus your 8x8 binary image is going to be construed as a 64-dimensional hypercube in the first hyperquadrant. The algorithms then use geometric analogies to find clusters. Distance, with K-means, shows up as Euclidean distance in 64-dimensional space. It's one way to do it.