What is the origin of the idiom "to be sure"?
Sure and collocations with forms of to be came from French; the idiomatic usage appears to be an idiomatic phrase that in the 17th century was pared down to a standalone adverbial.
Oxford English Dictionary
As both an expression of certainty and a concession of a (sometimes unfortunate) fact, to be sure fits the meaning in "sure, adj., adv., and int.," P7.b.:
b. As a sentence adverbial: (in affirmative use) for a certainty; certainly, undoubtedly, of course; (in concessive use) it must be admitted, indeed. Also in well, to be sure! as an exclamation of surprise (cf. well, I'm sure! at Phrases 9b).
The OED cites examples as early as 1615 and 1657. To track it further back, I had to look in an Anglo-Norman dictionary.
Early French Usage
This form - to be sure - has a correspondent in Anglo-Norman, the medieval French dialect that sure came from in the fourteenth century. Here is the entry for seur[1]. Among uses meaning certain, sure, resolute, reliable, safe, and secure, there are also several phrases, including estre a seur and estre en seur - literally the infinitive for to be and sure with a preposition between them. As the examples show with different verb forms seez, soit, seit, the verb could vary:
1 to be safe: (Tristran and Iseut) Bien quidoient estre a seor. Sorvient i par estrange eor Li rois Trist (C) 3;
2 to be assured: Il li rendrat, seez a seur View TextResur (C) 217;
3 [law] to be guaranteed: issi que yl face grey al vendour et quy il soit en seur del soen View TextOak Book i 38;
4 to be accountable (for): e le bailiff seit a seur de toutes choses que coustume deyvent de entree View TextStats I 46
The tendency to use a form of to be with sure would continue into English.
Early Modern Use in French and English
In French, this usage would continue into the seventeenth century in early dictionaries like Nicot, Thresor de la langue française (1606)
Estre seur et asseuré de quelque chose, Sçavoir certainement, Exploratum habere aliquid. (to be sure and assured of something, to know certainly, to have investigated something.)
In Thomas Cooper's Thesaurus Linguae Romanae et Britannicae (1578), the same Latin (Exploratum habere) is translated, "To know for suretie: to be sure of"
Early uses of "to be sure" most often integrated into the syntax of the sentence, like this from a 1604 sermon by Lancelot Andrewes, where to be sure heads a longer string (to bring us to regard):
Then to be sure to bring vs to Regard, he vrgeth this, Perteines not all this to you? Is it not for your good? Is not the benefit yours?
It is likely that this to be sure usage evolved into a standalone idiom. Sorting through a few of the 7000+ results "to be sure" yields in Early English Books Online, An apologeticall narration by Thomas Goodwin (1643) shows a possible early idiomatic usage, where to be sure appears as a parenthetical to signal the certainty of a remark:
We found it also gran∣ted by them all, that there should be several El∣ders in every congregation, who had power over them in the Lord; and we judged that all those precepts, obey your Elders, and them that are over you, were (to be sure, and all grant it) meant of the Pastours and Teachers, and other Elders that were set over them in each particular congregation re∣spectively, and to be as certainly the intendment of the holy Ghost, as in those like commands, Wives obey your owne husbands, Servants your own governours, to be meant of their several Families respectively.
The phrase feels fully established in later results. For example, in Marcelia by Frances Boothby (1670), a character named Lucidore says:
It is as much as I desire that I am certain it is one of your attendants: for where Marriage is made, and that a ser∣vant to neither party, there is always to be sure but beg∣garly house-keeping, and I love good company as my life.
So the phrasal usage "to be sure" was present in Anglo-Norman, appeared frequently in Early Modern English, and eventually became an idiom that functions as an adverbial.