If you break it down, 公路 means public road, which does not mean highway. So why does every dictionary say 公路 is highway?
A highway IS a public road, so there is no problem calling it a 公 (public) 路 (road).
Let's step back a little and consider this: If you break down the English word "highway" into "high" and "way", a learner coming from a different language background may well be wondering why. Since a highway is not necessarily high in elevation, why call it a "highway"? And why call some roads "freeway", when they are not really free? I have been on many freeways that charge you a toll to use.
When learning a language, it's important to realize that this is an entirely different system that has developed over time into what it is now, mostly independent of other languages. True, some languages are related and have certain things in common, but we must not assume that something that you've accepted in your language has to be true in another, especially when the two languages are as different as Chinese and English.
I think your question itself is a bit Anglo-centric. The fact that highways are called "highways" in English isn't necessarily derived from logic, as I tried to show above. It is just a word that has developed over time to denote a road that is mostly used by motorists, has few traffic lights, allows a higher speed than other city streets ... etc. The fact that this same road is called 公路 in Chinese probably came about in a similar manner. Note I say "probably" because I have not delved into the etymology of the word 公路. The point I am trying to make is, when you learn words in a new language, it's better, and easier, to just accept the term, without analyzing its components from the perspective of your native language.
Finally, a note about the comment you made. You asked: "but aren't most roads public? so wouldn't it be difficult to differentiate between roads?" No, it would not be difficult to differentiate between roads, because other roads have other words designated for them. For example, a city street is 街 or 街道, a back lane is a 巷 or 後巷. When coining a word in a language, it does not have to be a strict logical process in that when I choose the word "public", I need to exclude everything that isn't public. It's great to be curious, but looking at every single word as something to query from the standpoint of your native language will be futile and incredibly frustrating.
highway means 'a main road especially one connecting cities and towns', so highway is a road 'connecting' cities and towns.
same does 公路 means
another kind of road is city road, I do not know if in English there is a word describing city road, but in Chinese traffic rules, it states clear that city road means '城市道路’, which is 'IN' the city.
in short, 'highway' or 公路 is 'CONNECTING' cities and towns, while 'city road' or 城市道路 is roads 'IN' a city.
so why is it called 公public路？ i would say this 'public' is in terms of state(or province-wise public. a city controls its city road. but a city cannot control 公路. so it is called public.
but after all, it is okay to say 公路 to refer to any kind of roads nearly everywhere, so don't be too restrained by its definition. nobody care that much