The following is a (partial self-)answer both in the positive and in the negative
direction.
Lemma A.
Assume that there are at least $n$ distinct non-zero values of $v$, i.e., $n$
leaves whose corresponding $v$'s are all non-zero and distinct. Then
$\dim V \geq n/k$.
This Lemma follows from Lemma B below; just prune leaves whose $v$ appears
as the $v$ of some other leaf until no such repetitions are left, and orient
all edges of $T$ away from the root, thus making $T$ into a directed graph.
(Actually, let me denote $v$ by $u$ from some on, so that there is no confusion with the use of $v$ to denote a vertex.)
In a directed graph whose edges have labels of the form $\pm x$, we associate
a formal linear combination of letters $u(\phi)$ to a (directed) path $\phi$ in the obvious way: edges traversed against their orientation in a path are counted with their signs flipped.
Lemma B. Let $\Gamma$ be a connected, oriented graph where every edge has a label of the form $x$ or $-x$ for some letter $x$. Assume that every
letter appears in at most $k$ labels. Let $S$ be a set
of $n$ vertices in $\Gamma$. Assume that, for every pair of distinct
elements $v, v'\in S$, any path $\phi$ from
$v$ to $v'$ satisfies $u(\phi)\ne 0$.
Then the space $V$ spanned by all such paths has dimension $\geq (n-1)/k$.
Proof of Lemma B.- Let $v, v'$ be any two distinct elements of $S$. Let $\phi_1$ be a path from $v$ to $v'$. Choose any edge $e$ in $\phi_1$, and say that its label is $x$ or $-x$. Now remove from $\Gamma$ every edge with the label $x$ or $-x$. We obtain a graph with at most $k+1$ connected components (some of them possibly consisting of a single vertex). Choose any connected component containing at least two distinct elements of $S$, and iterate: let $\phi_2$ be a path from one to the other, etc.
After $r$ steps, we have a graph with $\leq r k + 1$ connected components. We stop when there is no connected component containing at least two elements of $S$; that
can happen only if $r k + 1 \geq n$, i.e., only if $k\geq (n-1)/r$. We have paths $\phi_1,\phi_2,\dotsc,\phi_r$ such that, for every $1\leq i\leq r$, there is a letter $x$ appearing in $u(\phi_i)$ but absent from $u(\phi_{i'})$ for all $i<i'\leq r$. Hence the span
$\langle u(\phi_1),u(\phi_2),\dotsc,u(\phi_r)\rangle$ is $r$-dimensional.
End of Proof of Lemma B.
Now, the problem in applying Lemma A to my original question resides simply in that there may not be many distinct non-zero values of $v$. In fact, it could be that $v$ is the same for all the leaves for a tree with $2^m$ leaves and height
$2 m$, and yet $k=2$. (For instance, for $m=2$, let $T$ be a tree with paths from the root to the leaves given by abcd, abdc, cdab, cdba, with branching in the natural way: the edges containing to the root are labelled a and c, those edges lead to edges b and d, those fork out into c and d and into a and b, respctively, etc.) It may be that $r$ is always large for such examples, but it might not be; perhaps someone wants to construct a counterexample to my original question with low $r$?
