Task-oriented communications for multi-modal applications emerge with the intelligence-oriented evolution of Internet of Things, where massive computation offloading with heterogeneous streaming requirements greatly challenges the existing mobile networks. Compared with semantic coding which reduces intra-modality redundancy by feature extraction, cross-modal coding further exploits inter-modality association and thus acts as a promising solution. However, unresolved information-theoretic issues hinder its full promise: 1) how to characterize the achievable region of cross-modal coding for task-oriented communications, and 2) to what extent can task-oriented communications benefit from exploiting inter-modality association. Therefore, this work first establishes a cross-modal rate-distortion function for task-oriented communications, and proves the feasibility of optimizing its information-bottleneck inspired transformation for guiding the design of learnable codec. In particular, the optimal feature representation is specified by a converging iterative solver under perfect statistical knowledge. Second, we prove a new bound on compression gains of cross-modal coding in task-oriented communications, based on a sufficient condition for cross-modal representation to be effective. Furthermore, a typical learnable codec is designed, whose loss function can be theoretically interpreted by our derived results. Finally, experimental evaluations verify the positive correlation between cross-modal coding gains and inter-modality association levels.