I haven't seen Mystic River, so I don't know how big Eli Wallach's role is and I don't recognize Olivia Williams enough to look for her in X-Men: First Class, so I can't speak to these two specifically but, on the topic of Cameos:
The Wiki article for "Cameo appearance" pretty much does all of the answering.
These roles are generally small, many of them non-speaking ones, and are commonly either appearances in a work in which they hold some special significance (such as actors from an original movie appearing in its remake), or renowned people making uncredited appearances.
And why aren't they credited?
Cameos are generally not credited because of their brevity, or a perceived mismatch between the celebrity's stature and the film or TV show in which he or she is appearing. Many are publicity stunts.
Some performers opt not to take credit for a project. They will do this either for professional reasons (they don't want to be associated with a really bad film) or because the process of working on the film was unpleasant. For example, Don Cheadle in Ocean's Eleven refused to be listed in the credits:
KW: I’ve noticed that you sometimes appear uncredited in movies, like in Ocean’s 11 [sic] and Rush Hour 2. Why is that?
DC: For different reasons. I did Rush Hour 2 just as kind of a laugh, so I didn’t really need a credit. To me, it was fine if people recognized me. And if they didn’t, that was fine, too. With Ocean’s, there was some stuff that happened behind the scenes that I didn’t like how it went down, so I just said, “Take my name off it.”
The situation must have gotten better, though, as he came back for two more films, in which he was credited. With Rush Hour 2, I'm guessing that fits more into the cameo-type appearance.
There's another possible explanation... as hinted at above when they say non-speaking roles... if a performer doesn't say anything on screen they can be considered an extra and extras never get credited. Even when cast in a speaking role, if all of a performer's lines are out of the final edit, they may not get credit.
As to pay
Extras get paid very little in films, even if a film is shot in an area where SAG has extras jurisdiction (SAG extras in theatrical projects currently make $157/day for 8 hours). If there's no SAG jurisdiction, they usually get paid minimum wage.
Speaking roles in SAG films get paid on a daily or weekly rate depending on the number of shooting days for their role. Bigger name performers can earn double or triple scale or, if they're big enough, can set their own salary. Sometimes, they will work out a no-quote rate with a lower budget project they just want to work on, which means they're taking less than usual on a project but it's in their contract that production can not divulge what the performer made. They will still get credit and will often say, "I'm taking a pay cut, give me a single or shared card at the beginning/end rather than just putting my name in the scroll"... and sometimes they'll get it.
The current SAG Rate sheet good through mid-2017 for full-budget Theatrical projects can be downloaded from their site here.
SAG doesn't set rates for big name talent, their agents and managers do, so talent can take as little as they want provided it's, at minimum, SAG scale.