Hi Plunkett
The Baliols, specifically John Baliol were the most obvious heirs to the Kingdom of Scotland after the accidental death of Alexander III and the death of his only heir "The Maid of Norway". Another claiment "the Bruce" was over-ruler by Edward of England sitting as judge and arbitrator.
The Baliols were generally weak and not able to stand up to Edward who tried to annex Scotland. This was the difficult time of William Wallace and the eventual winning of the War of independence by Bruce at Bannockburn.
The Baliols and Bruces were bitter enemies and the Caldwell's prospered under the Bruce and later Stewart administration. Therefore it seems at first unlikely that the Caldwell's were Baliol adherents. However the location of Caldwell in North Yorkshire so close to the original homeland of the Baliols is worth noting. The Scots teritory of all these families is strongly located in the Galloway to Glasgow area but the Caldwell's are from Ayrshire-Renfrew and are not well represented in Galloway.
This leads one to think that the Caldwell's are more closely associated with the Stewarts.
However the Baliols had lands in the Renfrew/North Ayrshire area which were later forfeited to the Stewarts. Additionally Hugh de Morville is supposed to have come to Scotland from Northumbria and settled right in the middle of what is now "Caldwell country".
A Knight by the name of Caldwell is mentioned as coming to Scotland in the train of de Morville in 1197.

BUT - to confuse matters - the only Morville I can find in England is in Shropshire near Much Wenlock. The Stewarts are supposed to have come from Shropshire also. Much Wenlock is the site of a Benedictine Monastery and I have heard it put that "Called - well" is merely a rough English translation of "Bene - Dicte". To give it its due I think that this is one of the more fanciful ideas.
We can go round and round in circles with this surname. It seems simple enough but the deeper you probe the more confusing it gets!
Further one of the first reference to Caldwell in Scotland is in 1292 and refers to a Caldwell associated with the Monastery at Paisley.