I agree that the birthplace in the 1861 census says Amandale but I assume this to be an enumerator's misreading of Annandale. Armadale is possible, as suggested, but that would require the enumerator to have made two errors.
https://maps.nls.uk/view/00000269 is a map showing Annandale.
https://maps.nls.uk/view/74400173 and
https://maps.nls.uk/view/74400175 show the parishes in and near Annandale, so you are looking for a baptism in one of those parishes.
His age in 1861 is listed at 55, which, if it is accurate, implies that he was born between 8 April 1805 and 7 April 1806. This is consistent with the 1851 census, which says he was 45, the 1871, which says 65, and the 1881, which says 75.
However the 1841 says he was 34. If accurate this would give a birth date between 8 June 1806 and 7 June 1807. As these dates don't overlap with the 1851, either the 1841 age is wrong or the 1851, 1861, 1871 and 1881 are all wrong.
Did his father's name come from his marriage certificate?
Unfortunately there is no readily available record of the baptism of a son David to a father named John Scott anywhere in Dumfries-shire between 1800 and 1810. So either there never was a record of the baptism, or the record has not survived, or there is a small possibility that he was baptised in a denominations whose surviving registers are not among those digitised by Scotland's People, for example the records of the Scottish Episcopal Church. Their surviving records are still in the churches, or in diocesan, local or university archives, and it takes a bit of sleuthing to find them.
As David's father was a 'gentleman', it would be worth looking though the wills and testaments on the Scotland's People web site.
To see if John Scott owned land, it would be necessary to consult the Register of Sasines, but that requires a visit to the National Records of Scotland, which is currently closed because of Covid-19 and unlikely to reopen before March 2021.
