Hi,
you are correct in that you need to replace the Gatekeeper with a VCS-C (And I would also consider replacing the Border Controller with a VCS-E so that you get SIP support across the board).
The MPS 800 should interop fine with Lync, but if you want features such as Multiway or a Telepresence Conductor integration you would have to deploy an MCU such as the Cisco Telepresence 4500 or 5300 series MCU or similar.
- Andreas