The tricky part is that a de facto rule is unlike a de jure rule, it's hard to pinpoint its origin as it is not based in law. The more I dig, the more it seems it is indeed a de facto rule that found its way to Annex 11.
It would take a team of aviation historians hunting through countless meeting points to get to the bottom of it.
However, I gathered some clues, mostly in reverse chronological order:
For the 250 knots during climb I found:
ICAO's REVIEW OF NOISE ABATEMENT PROCEDURE RESEARCH & DEVELOPMENT AND IMPLEMENTATION RESULTS
Target climb speeds are given as V2 plus, no attempt was made to specify the actual target speed as it is accepted that the segment is flown to the manufacturer’s specified safety speed.
It just so happens 250 is a numerical rounding that matches most aircraft, except for heavies loaded up for long-haul flights.
Numerous parties were involved:
... various parties, including universities, regulatory agencies, manufacturers, air carriers and airports.
So everyone came together, and agreed to 250 knots. But that's recent and has to do with noise.
ICAO Journal TOWARDS A PERFORMANCE-BASED NAVIGATION SOLUTION
Pilots should also avoid airspeeds of more than 250 knots below 10,000 feet above ground level (AGL), especially at times of the year when birds are migrating. Aircraft speed is more critical than bird size (body mass) in causing collision damage.
Someone should tell the geese to stop flying at FL400. (Related post.)
Activities of the European Office from 1954 to 1958 (link)
They discussed the advent of the jet age, and how the prop aircraft speeds of 250 knots are being exceeded leading to research into the consequences.
At that time, namely what affected the ATC and navigation systems because jet planes were relatively crossing sectors much faster.
It's not much but this section hints at the origin of 250 knots:
... significant increase in cruising speed of the jet-aircraft over the propeller-driven airline [...] around 400 knots = 750 km/h versus 250 knots = 450 km/h ...
REPORT OF THE EIGHTEENTH MEETING OF THE APANPIRG ATM/AIS/SAR SUB-GROUP
Appendix 4 to Annex 11 speed limitations of 250 kt below 10 000 ft AMSL are required for certain airspace classes.
Annex 11 history:
In October 1945, The Rules of the Air and Air Traffic Control (RAC) Division at its first session made recommendations for Standards, Practices and Procedures for Air Traffic Control. These were reviewed by the then Air Navigation Committee and approved by the Council on 25 February 1946. They were published as Recommendations for Standards, Practices and Procedures—Air Traffic Control in the second part of Doc 2010, published in February 1946.
Chapter 2
2.6.3 The requirements for flights within each class of airspace shall be as shown in the table in Appendix 4.
Appendix 4 lists the now de facto limit.
It doesn't say why, so it's most likely it's what everyone agreed on at that convention and consequent meetings.
8 December 1959 is likely the date when an amendment was added to Annex 11 that detailed those figures in Appendix 4 we now know.
That's 8 years before the FAA. Check this post for the FAA's side of the story if interested.
Without access to meeting points, that's the most I could find.
Short version of the above:
At numerous conventions and meetings beginning in the 50's, many parties met again and again to discuss the jet-to-prop traffic separation, the noise impact of jet planes, and the dangers of bird strikes. They concluded V2 plus speeds should be used, but since civilian jet aircraft have the same performance more or less, the 250/10,000 rule found its way to the requirements of airspaces.
It's not hard evidence, but given what I found, it's not far fetched to assume the above is correct. Over to you.