Ok, depois de algumas boas horas de trabalho, acabei com uma solução:
convert template.tif ( barcode.png barcode.png -negate -alpha off -compose copy_opacity -composite -colorspace CMYK +level-colors "cmyk(100%, 87%, 11%, 1%)" ) -geometry +123+321 -compose over -composite output.tif