Hi.
We are going to allow a couple of partners to communicate with our users via Lync. Do I need to buy CAL (for Lync) for every client from federated partners?

No, from the License Guide

3.2.1 Federated Users
A federated user is an external user that possesses valid credentials with a federated external
Lync deployment and is authenticated on that basis by Lync Server 2013. Federation is a feature
provided with the licenses of Lync Server 2013. Users connected by federation with another Lync
deployment do not require a CAL as the federated party will already own the appropriate
number of licenses.

No is the answer here. Like Holger mentioned, there is no such CAL requirement for federation or external access. I recall there was such requirement when it was OCS days, but with Lync, it does not necessary