The Duke Ellington Story on Records (DESOR) reports 7 other instances of Duke performing Carolina Shout between '65 and '73, all but one unissued. It looks like it was a regular part of his repertoire at that time. Of course he might also have performed it earlier but by the mid 60's nearly every EKE performance was recorded by soneone so we have a better record from that time on.