You're right, information were ambiguous.
To summarize, download, and unpack (if Safari doesn't do it for you automatically) the ZIP file at
https://github.com/bSr43/FixIDSRegion/releases
You need to launch the program using the Terminal application, which is located in the "Utilities" folder of the Finder. You can reach this folder by pressing ⌘⇧U in the Finder, or using the Finder's menu "Go > Utilities" (I don't have the correct English translation, as my system is installed in French, sorry about that).
Once launched, you can drag and drop the FixIDSRegion utility into the Terminal window: this will paste the exact location of the program on the disk. You'll probably see something like:
"/Users/yourname/Downloads/FixIDSRegion" appearing in the window.
Add the arguments to this command, ie, something like:
R:FR +330000000000
The exact arguments depend on the region where you live. If you are in the UK, it would be "R:UK +4400000000000", etc. The first part is the "R:" string, followed by the country, and the second part is a template international number for the country.
Once done, press enter. You'll be prompted to enter your password: this is to allow the program to modify a key on your behalf in the Keychain system program.
After that, launch Messages. You'll, once again, be asked for your password: this is because the key has changed, and now, you just need to allow Messages to access it again. So, in this case, choose the option to always allow access to the item (once again, sorry about that, I don't know the exact sentence in the English version).