To be strictly accurate this sentence should read "Our story of the Hall/ King-Hall family..." as neither James HALL or his elder son, James Frederick HALL ever used the surname of KING-HALL.
It was first used by his son William. When William was christened in 1820 he was given the second christian name of King as a mark of respect to his godfather and close friend of his father, Captain James KING, commanding officer of HMS Jason. This practice of using the surname of a friend as a christian name for ones children appears to have been quite common in the 19th Century. Two of William's sons, George and Herbert, were named Fowler and Goodenough, respectively, after close friends of their father.
According to family tradition William decided to turn his second christian name into part of his surname when he was promoted Captain in the early 1850s, because he wanted to differentiate himself from another Captain William HALL who was serving in the Royal Navy at the time. Apparently this namesake was inclined to write rather intemperate letters to The Times which our William did not wish to be associated with.
We cannot be certain whether this was the real reason for the change of surname, but evidence does suggest that the timing is accurate. We have letters from the 1830s and 40s that were signed William King Hall but these do not tell one whether King is being used as a Christian or surname. The earliest example we have where KING appears to be part of the surname comes from the Captain's Log of HMS Bulldog, where an entry, in March 1854, is signed W. KING HALL. There are number of other examples of this form of signature in correspondence and documents while he was Captain of Exmouth (1855-6) and Calcutta (1856-9).
William's attempts to change his surname seem to have been very gradual and rather haphazard. For instance seven of his children, born between 1854 and 1868 were registered under the name of HALL and only his last child, Baldwin, born in 1868 had the initial K included in his entry.
Successive editors of the Navy List also seem to have had a problem. Not only did William's entry in every alphabetical list appear under H, but so did those of his two son's, whose entries clearly showed that KING was part of their surname. In fact it wasn't until 1919, when William's grandson, Stephen KING-HALL, was serving at the Admiralty that the problem was finally sorted out and the KING-HALL entry appeared under K. Having said that, Stephen's entry under Lord KING-HALL, as he later became, appears in the latest edition of the Dictionary of National Biography under the letter H!