Below is a newspaper article from 1753 which is the earliest report I've found on the story that Jews believed Oliver Cromwell may have been their messiah. The article consists mostly of an extract from a French book published in 1691 (François Raguenet's Histoire D'Oliver Cromwel).
The London Evening Post
Tuesday, November 20, 1753
To the AUTHOR,
The account of the Jews inquiring into the pedigree of Oliver Cromwell, in order to set him up for their so long expected messiah, was but little known, until the author of An Answer to the Considerations laid it before the public : It has been since a common topic of conversation, and therefore I hope it will give an entertainment to the curious, to read an extract of this affair, taken from Raquenet's History of Oliver Cromwell, in 410. Paris 1691, P. 321, 322, &c.
The affairs of the Protestants in the valleys of Piedmont being thus settled, Cromwell, who had no longer any foreign business to engage his attention, applied himself to reform the abuses which he observed had crept into the republic.—He began this work by the retrenchment of all superfluous expenses, which principally regarded persons of quality ; he moderated the excess of sumptuous entertainments, the pomp of equipages, the magnificence of furniture, and the richness of apparel, by a great variety of proclamations, in which he descended to to minute a detail, that it appeared ridiculous to the great, but it charmed the common people, whose favour he chiefly aimed at in this affair: He even went so far as to allot the very number of servants, that each according to his rank should be permitted to keep, and abolished every thing that had any shew of luxury and pride.
After this, he made a positive prohibition against all games of hazard, under very severe penalties : He enacted very rigorous laws againft usurers, and established so many other regulations, for the good of religion, the peace of the state, the security of commerce, the adminstration of justice, and the support of all other Christian and civil virtues, that the Puritan ministers no longer spoke of him in the pulpit but with admiration, and the people began to look upon him as a divine man : In short, his reputation grew to such a high pitch, that the Jews in Asia having heard the many great things that were said to be done by him, by the voice of fame, which did not fail to exaggerate matters more and more in proportion as she carried them to greater distance, came to a resolution to send some of their own people into England, in order to inform themselves, whether he was not the deliverer or redeemer whom they expected, and whom they have constantly believed they should find among the Number of those extraordinary generals who have made their appearance in the world since their dispersion.
They pitched upon for this embassy the famous Jacob ben Azahel, who had orders to take along with him, as he passed through Bohemia, David ben Eliezer, rabbi of their synagogue at Prague, who was a complete master in all the languages of Europe, and Rabbi Menasseh Ben Israel of Amsterdam, whose office it was to serve them by way of guide.
1656. When they were arrived at London, in order to conceal the true design of their going thither, they at first only produced a credential relating to the establishment of a company for the carrying on a commerce to the Levant, from which they pretended the English would reap great advantages. The commissioners of the Board of Trade received them with joy, and the proposals they made were very favourably listened to ; but as these could not be received without introducing a new sort of religion in the republic, they sent them back to Cromwell, in whose hands alone was lodged the power of doing it in quality of Protector. Cromwell too, in the same manner, gave them a very gracious reception, in consideration of commerce, which he hoped might become more flourishing in England by their means: He even granted them a private audience, which they asked of him, in which these two Jews having intimated to him the great esteem in which they held the famous Library of the University of Cambridge, Cromwell, who could not tell how to forgive the zeal which this university had shown for the late King, promised these strangers to sell them all the manuscripts, with whatever other books they should find there most curious and valuable.
They then went a second time to review the books and take a catalogue of their number, and the condition they were in, which they did in presence of the librarians who showed them to them, thinking at the same time that they had no other design in this, than to satisfy their curiousity, agreeably to what they declared : Bur after this, instead of returning stright to London, they took occasion, by means of this journey, to convey themselves, in prosecution of the principal design of their embassy, into Huntingdonshire, where the parents of Cromwell were originally born ; and this with a view to inform themselves about his birth, and to learn from those who might be best acquainted with his pedigree, whether there were never any among his ancestors descended from Hebrew blood. Whatever precautions they might have taken to keep this senseless enquiry a secret, it was not possible for them for them to contrive it so as that it should not be discovered ; the News of it soon spread itself in London, and occasioned many stinging railleries against the Protector, who conceived fso sharp a resentment from it, that he refused these unfortunate Jews not only the liberty of commerce, and the purchase of the library of the universty of Cambridge, which he had flattered them with the hopes of, but moreover declared to them, with great warmth, in a very solemn audience which he had expressly given them for that purpose, that the republic and he made profession to adore a crucified God, and they would by no means consent to have any trade carried on with those whom they looked upon as his most irreconcilable enemies ; and at the same time dismissed them, without allowing them the liberty of making the least reply. But whatever were the artifices Cromwell had recourse to, to persuade the people that the zeal which he had for the Christian religion had been the cause of his rupture with the Jews, this did not hinder all the world from seeing that his resentment had been his sole motive to it. This appears plainly from a small libel that was handed about at that time, entitled, Cromwell, the Lion of the Tribe Judah, in which what I have just now been relating about the deputation of the synagogues of Asia and Germany, was exposed with the smartest reflections and inmost delicate raillery that could be imagined upon this subject against the Protector.