You already mention homing pigeons. Another alternative is to use sound and a suitably shaped reflector to focus the sound beam toward the receiver, who will in turn use a similarly shaped receiver to listen.
Something similar was used during WW1, where acoustic mirrors were used to detect enemy planes flying toward England over the Channel.
Since you are in the pre-electric era, you cannot use a microphone, but you have to sit a person in the listening station.
Small explosive charges or cannons can be used as means of producing loud sound, which should allow reaching greater distances. This would however limit the transmission rate.
Wind and temperature gradient might influence the propagation direction, and background noises (think of a thunderstorm) might likewise affect the signal to noise ratio.