How to add a element with walker menu right after begin of the navigation tags?

The question is unclear but wp_nav_menu() has a couple of arguments that will allow you to add classes to the output. For example…

wp_nav_menu(
  array(
    'container_class' => 'conclass',
    'menu_class' => 'menclass'
  )
);

You can alter those arguments using the wp_nav_menu_args filter as well.

However, I suspect that when you say “class” you are using the wrong term, and what you actually want to do is add a single list item to the beginning of the navigation menu. Your filter is pretty close:

function add_li_to_nav($items, $args) {
  remove_filter('wp_nav_menu_items', 'add_li_to_nav', 10, 2);
  $items="<li>SEARCH</li>".$items;
  return $items;
}
add_filter('wp_nav_menu_items', 'add_li_to_nav', 10, 2);

That will add the “search” list item before the current item, and then remove itself so that the “search” list item will not be added in any other locations.

Update based on new information:

By far the simplest solution is going to be to pass wp_nav_menu() a 'container'=>false argument and write the rest into the markup.

<nav id="primary-navwrapper" class="pushy-right">
  <!-- SO HERE RIGHT AFTER NAV PLACE THE FOLLOWING ANCHOR TAG -->
  <a href="#">mobile</a>><?php
  wp_nav_menu(
    array(
      'container' => false
    )
  ); ?>
</nav><?php

Another option is to filter wp_nav_menu:

function add_anchor_to_nav($menu) {
  remove_filter('wp_nav_menu_items', 'add_anchor_to_nav', 10, 2);
  $pat="(<nav[^>]+?>)(.*)";
  $menu = preg_replace('|'.$pat.'|','$1<a href="#">mobile</a>$2',$menu);
  return $menu;
}
add_filter('wp_nav_menu', 'add_anchor_to_nav', 10, 2);

wp_nav_menu(
  array(
    'container' => 'nav'
  )
);

regex on markup is dicey but this is fairly simple. I think it will perform relatively well.