Restitution de la caution

Bonjour,
J'ai rendu mon appartement le 31 Janvier 2021, cela faisait 3 ans que nous étions dedans. Nous avons déménager le 15 janvier pour nous laisser 15 jours pour nettoyer car les radiateurs électriques assez vieux avaient fais de grosses traces noir absolument partout(murs, plafond, placard..).
Nous avons demandé conseils à l'agence, car quand nous sommes rentrés dans l'appartement tout avait été refais à neuf. Ne voulant pas perdre la caution, nous avons suivi à la lettre les recommandations. Nous leur avons demandé si nous devions tout repeindre après avoir lessivé les murs et le plafond, ils nous disent que non.
Lors de l'état des lieux, la personne représentant l'agence nous a dit qu'il n'y avait pas de souci à se faire et que nous allons certainement récupérer peut être pas l'intégralité mais une bonne partie de la caution.
Au bout d'un mois d'attente je les relances pour la caution le 9 mars 2021. L'agence m'envois des devis réalisés par une entreprise pour les travaux qu'ils ont du réaliser dans l'appartement pour effectuer de la peinture! Donc il ne me rendrons pas la caution et il me demande en plus environ 500 euros pour les travaux réalisés. Vous comprendrez que bien sur, cela à été une mauvaise surprise de s'avoir que je perdais ma caution et en plus que je devais leur 500 euros.
Qu'est-ce que je peux faire? Quelles sont mes recours possibles ?
Merci à vous,
Mathilde