Calculate the sum at a level of a binary tree represented in a String
Recursion:


  Considering this is a binary tree, a recursive function seems
  appropriate.


Recursion would be a natural choice if your input were a root tree node with tree nodes as children - a recursive data structure. However, your input is a 'flat' string representation of a tree. A simple iteration might actually be much easier to implement, read and execute.

Passing inputs:


  How should I properly be passing the altered string throughout the
  recursive function?


I think the recursive passing down of substrings representing nodes or node lists (children) is already pretty well done.

However, I would like to suggest a few improvements regarding the parsing functions and their return values:

Style:

Consider the getCurrentVal(input) function:

function getCurrentVal(input){
  var val = "";
  while(input[0] !== "(" &amp;&amp; input[0] !== ")" &amp;&amp; input.length){
    val += input[0];
    input = input.substr(1);
  }
  return {
    val,
    input
  }
}


The code is not very descriptive: It is not immediately obvious what this function does. 


The function name getCurrentVal is misleading, as you don't just return the node value, but also the children. 
The argument name input is meaningless, as all arguments are inputs.
The variable names are misleading, as you reuse input to store part of your output.


How about this alternative:

// Split node 'a(b)(c)' into value 'a' and children '(b)(c)':
function parseNode(node) {
  let split = Math.min(node.indexOf('('), node.indexOf(')'));
  if (split &lt; 0) split = node.length;
  return {
    value: node.slice(0, split),
    children: node.slice(split)
  };
}



'Parse' hints at the input being text or some other raw content.
'Node' carries more semantics than 'input'
Math.min and String.indexOf are more descriptive than a while loop.


Destructuring the resulting object improves readability:

var {value, children} = parseNode(node);


Also, when parsing integers, you shouldn't use JSON.parse(string) but the more specialized Number.parseInt(string) or the idiomatic type conversion via +string.

Further naming suggestions:


getValueForLevel -> getSumForLevel or sumTreeLevel
Consistency: Choose either val or value when naming currentValue.val, getCurrentVal, getValueForLevel


Complexity:


  Considering the parens and values are removed as they are parsed, that
  lends itself to O(n), but I feel it's O(n^2) because of the duplicate
  parsing in order to create the child nodes. Is that correct? Can it be
  improved?


First of all, let's define n as the length of the input string.
Then, let's look at the complexity of the helper functions:


stripFirstLastParen: O(n) because of input = input.substr(1)
getCurrentVal: O(n²) for worst-case input "1(2)(3)", "11(22)(33)", "111(222)(333)" and so on because of input = input.substr(1) within while (input.length). Yes, we break the loop as soon as we encounter the first parenthesis, but this doesn't happen before parsing roughly 1/3 * n characters for above input. The best-case complexity is however O(n) when the value has constant length.
getChildren has worst and best-case time complexity of O(n²) due to input = input.substr(1) within a while loop over input.


Now, we can tackle the complexity of getValueForLevel:


The first four lines are dominated by getChildren(currentValue.input). If the length of currentValue.input - the length of the children - is proportional to n, then it has a runtime complexity of O(n ²).
Then it calls getValueForLevel(children.left, k-1). It is easy to construct inputs which maximize the length of children.left such as "4(3(2(1))))" without right children. For this input, in each iteration, the length of children.left is reduced by 3.
The final call to JSON.parse is in O(n).


Adding the complexities together gives us: 

n² + (n-3)² + (n-6)² + ... + (n-3k)²


Thus, for k = 0 the runtime complexity is in O(n²) and for maximum k we have a runtime complexity of O(n³):



In general, the runtime complexity is bounded by O(kn²).

Alternative approach:

Following my introductory remarks about a possibly simpler iterative solution, here a possible implementation with linear runtime complexity:



// Sum integer tree nodes at given level: 
function sumTreeLevel(tree, level) {
  let tokens = tree.match(/(\(|[0-9]+|\))/g);
  let sum = 0;
  for (let token of tokens) {
    if (token === '(') {
      level--;
    } else if (token === ')') {
      level++;
    } else if (level === -1)  {
      sum += +token;
    }
  }
  return sum;
}

// Example:
console.log(sumTreeLevel("(10(5(3)(12))(14(11)(17)))", 2)); // 43