Make the Catholic Church a bit less corrupt and decadent in the 16th century. The Scots will rally around it in the face of Protestant incursion. In particular, make Protestantism (in all its shades) a religion particularly associated with England.
Or, easier still, as someone has suggested, kill off John Knox.