I think you are on the right track with .htaccess and rewrite rules
What you might consider is a 301 redirect in your .htaccess like this
#fancy name redirect here
redirectMatch 301 ^/restaurant/london(.*)$ /?category_name=restaurants&locations=london
Basically you can then tell people to go to your own friendly URL and they get redirected to the longer one that WordPress uses.
I’d have a look at Perishable Press stupid tricks with .htaccess
As another point of reference you can use go to WordPress Admin > Settings > Permalinks and change the word Category to Restaurants — but that will mean all your ‘categories’ are now ‘restaurants’