Snow Blow My Driveway!
JavaScript (ES6), 346 310 299 298 297 296 283 bytes


f=(a,y=0,x=0)=&gt;(a[y][x]?a[y][x]=='O'&amp;&amp;(a[y][x]='*',(g=w=&gt;(w=a[y])&amp;&amp;w[x]&amp;&amp;(w[x]&lt;'!'?g(w[x]='v',y++)||g(w[x++]='&gt;',y--)||g(w[--x]='^',y--)||g(w[x--]='&lt;',y++)||+(w[++x]=' '):w[x]=='O'&amp;&amp;!/ /.test(a)?w[x]='%':0))(y++)||g(y-=2)||g(y++,x++)||g(x-=2)||+(a[y][++x]='O'))||f(a,y,x+1):f(a,y+1))
&lt;textarea id="tests"&gt;XXXXOOOOXXXX&amp;#10;X          X&amp;#10;X          X&amp;#10;XXXXXXXXXXXX&amp;#10;&amp;#10;XOOOOOX&amp;#10;X     X&amp;#10;X     X&amp;#10;X     XXXXXXXX&amp;#10;X            X&amp;#10;X            X&amp;#10;XXXXXXXXXXXXXX&amp;#10;&amp;#10;XOOOOX&amp;#10;X    X&amp;#10;X    X&amp;#10;X  XXX&amp;#10;X    X&amp;#10;X    X&amp;#10;XXXXXX&amp;#10;&amp;#10;XXXXXXXXXXXXX&amp;#10;O           X&amp;#10;O    X      X&amp;#10;O    X      X&amp;#10;O           X&amp;#10;XXXXXXXXXXXXX&lt;/textarea&gt;&lt;br&gt;&lt;button onclick="for(test of document.getElementById('tests').value.split('\n\n')){console.log(test);arr=test.split('\n').map(line=&gt;line.split(''));f(arr);console.log(arr.map(line=&gt;line.join('')).join('\n'))}"&gt;Run&lt;/button&gt;



Quite hacky in some places, but I wanted to get the code out there. Input as a 2D character array, output by modifying said array.
Ungolfed version
This is the same exact algorithm, save for some truthy/falsy magic with +' ' being NaN being falsy (and some more), some golf variables and using ifs instead of ?:, || and &amp;&amp;.
f = (a, y = 0, x = 0) =&gt; {         // main function
  if (!a[y][x])                    // check for end of line
    return f(a, y + 1);            // end of line, recursively check next
  if (a[y][x] == 'O') {            // check for valid start position
    a[y][x] = '*';                 // set the start position
    function g() {                 // pathfinder function
      if (!a[y] || !a[y][x])       // check for out of bounds
        return 0;
      if (a[y][x] == ' ') {        // check for snow
        a[y][x] = 'v';             // set current cell to 'down'
        y++;                       // move position down
        if (g()) return 1;         // see if a valid route is found from there
        y--;                       // if not, reset position and try again
        a[y][x] = '&gt;';             // repeat for other directions
        x++;
        if (g()) return 1;
        x--;
        a[y][x] = '^';
        y--;
        if (g()) return 1;
        y++;
        a[y][x] = '&lt;';
        x++;
        if (g()) return 1;
        x++;
        a[y][x] = ' ';             // no route found, reset cell to snow
        return 0;
      }
      if (a[y][x] == 'O'           // check for valid exit
          &amp;&amp; !/ /.test(a)) {       // and that no snow is left
        a[y][x] = '%';             // set the exit
        return 1;
      }
    }
    y++;                           // move a cell down from the start position
    if (g()) return 1;             // see if a valid route starts there
    y -= 2;                        // repeat for other directions
    if (g()) return 1;
    y++; x++;
    if (g()) return 1;
    x -= 2;
    if (g()) return 1;
    x++;
    a[y][x] = 'O';                 // no route found, continue on
  }
  return f(a, y, x + 1);           // check the next cell
}