As you say, there is no definitive date and it is a complex question but the traditional date that is given is usually following the defeat of Carthage during the Second Punic War, hence such quote from Sallust (War with Catiline. 10.1):

But when our country had grown great through toil and the practice of justice, when great kings had been vanquished in war, savage tribes and mighty peoples subdued by force of arms, when Carthage, the rival of Rome's sway, had perished root and branch, and all seas and lands were open, then Fortune began to grow cruel and to bring confusion into all our affairs.

Prior to the ending of the Second Punic War, there are examples of states requesting help from Rome, such as the Greek States against Macedon (Livy. 30.26):

Towards the close of the year a deputation came from the Greek cities in alliance with us to complain that their country had been devastated and the envoys who had been sent to demand redress were not allowed to approach Philip.

It is really from 201 BC onwards that we see more frequent mentions of foreign diplomacy of Rome within the east. Polybius' book 31 is filled with examples of foreign envoys arriving in Rome in other to acquire assistance and council. For example (Polybius.31.7.1):

Ariarathes, the king of Cappadocia, on the return of the envoys he had sent to Rome, thinking from the answers he received that his kingdom was now on a safe footing, since he had succeeded p175 in gaining the goodwill of the Romans, paid a thank-offering to the gods for his success and gave a banquet to his nobles.

Or (Polybius.31.8.1):

About this time legates arrived from Rome, in the first place Marcus Junius, to settle the difference between the Galatians and King Ariarathes.

And then you move on to the famous story of Gaius Popillius Laenas in 168 BC in which he instructed Antiochus to avoid war with Egypt (Polybius. 29.27.1-8):

At the time when Antiochus approached Ptolemy and meant to occupy Pelusium, Caius Popilius Laenas, the Roman commander, on Antiochus greeting him from a distance and then holding out his hand, handed to the king, as he had it by him, the copy of the senatus-consultum, and told him to read it first, not thinking it proper, as it seems to me, to make the conventional sign of friendship before he knew if the intentions of him who was greeting him were friendly or hostile. But when the king, after reading it, said he would like to communicate with his friends about this intelligence, Popilius acted in a manner which was thought to be offensive and exceedingly arrogant. He was carrying a stick cut from a vine, and with this he drew a circle round Antiochus and told him he must remain inside this circle until he gave his decision about the contents of the letter. The king was astonished at this authoritative proceeding, but, after a few moments' hesitation, said he would do all that the Romans demanded. Upon this Popilius and his suite all grasped him by the hand and greeted him warmly. The letter ordered him to put an end at once to the war with Ptolemy. So, as a fixed number of days were allowed to him, he led his army back to Syria, deeply hurt and complaining indeed, but yielding to circumstances for the present.

As you can see then, during the latter half of the third century BC is when Rome really became to be known within the Mediterranean territory as a power, but following the defeat of Carthage is when Rome began to be seen by other states as the power of the Mediterranean.