I don’t understand exactly why you chose to use a custom Nav Walker and how you managed to make it work. You should use this when you want to display the menu entries with a very specific html code that do not fit into the wp_nav_menu output. In your case, you want to change the link itself, not only the html formatting.
I think your request can be solved in an easier manner by using a rewrite rule. That rule will transform any custom formatted URL to another that matches the default WordPress format.
If I understand well you need, you will have to add the following rules :
add_rewrite_rule('^mediums/([^/]*)/([^/]*)/?','index.php?mediums=$matches[1]&project=$matches[2]','top');
add_rewrite_rule('^clients/([^/]*)/([^/]*)/?','index.php?clients=$matches[1]&project=$matches[2]','top');
Add this code to the init hook, and you should be able to achieve the desired result.
Now, to display the navigation menu, you should use the get_terms function to list your taxonomies terms and display the appropriated links.