A pesar de que hoy día se supone que la base es el sustantivo martín (tal como está recogida en el DLE), por lo que martines pescadores debe ser la forma plural siguiendo las reglas normales de hacer plural un sustantivo seguido por adjetivo (pescador es, antes que nada, adjetivo, significando que pesca).
Si tomamos pescador como sustantivo, frente a dos sustantivos, es posible conservar la forma singular de pescador, pero como nota el DPD:
si el segundo sustantivo puede funcionar, con el mismo valor, como atributo del primero en oraciones copulativas, tiende a tomar también la marca de plural
Y como «los martines que son pescadores» tendría sentido, la tendencia sería marcar pescador en plural.
No obstante lo anterior, abundan los ejemplos en que martín queda en el singular y pescador se modifica plural, muchos de ellos ligados con guion. Este guion parece ser la clave. Cuando se entiende una combinación de sustantivo y adjetivo como una sola entidad, lo normal es solo marcar el último elemento en plural: aguafuertes (y no aguasfuertes), arcoíris (y no arcosiris, aunque sí es válido arcos iris de arco iris), altavoces (y no altasvoces). Aunque lo más común sería escribir como una palabra, como es normal que las combinaciones de dos adjetivos sigan la misma regla de formación pero usando guion, tampoco sería tan raro encontrar un sustantivo ligado con guion a un adjetivo.
Con la notada presencia histórica de un guion, imagino que para algunos en el pasado (e incluso, buscando en Google, hoy en día) la combinación de martín-pescador se consideraba palabra compuesta y por lo tanto no se pluralizaba el primer elemento.
En fin, se podría defender cualquier de las tres opciones, aunque yo optaría por pluralizar ambas palabras.
