This seems reasonable and it looks good to me (as long as there is a later patch coming that calls the new method).
However: is there a situation where Contains() is preferable to Lookup()? It seems to me that in some cases you would want the looked-up value -- and in those where you don't there is no cost to return a pointer to it. As far as I can tell both ultimately end up as a call to find() on the AVL tree.
Even though there isn't a performance difference, I think it is semantically clearer since it is explicit that the value is unneeded.
The interface of ProgramState provides a contains() function that calls into Contains() of the underlying partial traits as part of its implementation. That function is present for ImmutableSet and ImmutableList, so it is inconsistent that ImmutableMap doesn't have it. I've been working on a Z3 constraint backend that uses this, though the implementation has been trickier than I expected.