Caraṇavyūha (चरणव्यूह), a work of Shaunaka mentions the association of Upavedas with Vedas in AtharvaVeda Khanda. As I've informed in this question I have not found its English or Hindi transnational yet and hence quoting original Sanskrit verse from Sanskrit book available on Internet Archive:
Transforming into IAST:
tatravedānāmupavedāścatvāro bhavantyṛgvedasyāyurveda upavedaḥ yajurvedasya dhanurveda upavedaḥ sāmavedasya gāndharvvedo’tharvavedasyārthaśāstraṃ cetyāha bhagavānvyāsa skando vā|
It syas:
- Rigveda's Upaveda is Aayurveda
- Yajurveda's Upaveda is Dhanurveda
- Samaveda's Upaveda is Gandharvaveda
- Atharvaveda's Upaveda is Arthashastra
Note: I am not sure whether Charanavyuha is the first text to mention the association but at least we now have scriptural-reference. Charanavyuha is many times used as reference for available Shakshas of Bedas.