Probably Kalki based his ideas on the fact that he was a king of region around Vallam and this was ruled by Vanars earlier. It is quite possible that Vandhiyathevan was one of the small regional leader who accepted chola suprimacy and had close links with them like many other regional leaders of his time.
One interesting thing to note is that - in chola dynasty since Aditya chola - it has been a trend to strengthen their ties through marital alliances. Right from Aditya, Parantha and Sundara we see kings marrying many daughters - sometimes from potential would-be enemy empires and forge solid relationship with them. And in case of VDevan , we see that he married Kundavai - perhaps the most powerful princess of her times. It's worthwhile to ponder whether this had any gains to chola empire. In this light, it makes sense to view VDevan as a east chalukyan price - because - later, we see Rajaraja forging very strong relationship with them by giving his daughter to Vimaladitya - who is of chalukyan origin. (This resulted in a completely different set of chola-chalukya clan - from the time of Kulothungan I). It is evident that Rajaraja would not have experimented this marriage unless he had a strong faith in their relationship. This could have been due to VDevan.
But things that contradict this idea are that VDevan never went to Chalukyan kingdom - he peacefully reigned few regions under Rajaraja and was one of the leading generals of the army. Thus, we see that the arguement lacks enough strength to be accepted as a fact.
So much about VDevan's origins !!
So, who this guy was - we might not know - but we do know something about WHAT HE DID.