O libzmq-dev não contém lib c zmq. Observe o "c" extra.
O libczmq é uma biblioteca diferente que aparentemente não é empacotada para o Ubuntu. Sua página da web diz que para o Ubuntu:
Installing ZeroMQ and CZMQ from source code is recommended.
Mais abaixo na mesma página, você encontrará instruções sobre como fazer isso.