Highly colored vertices in greedy coloring imply existence of subtrees
Let us prove the following claim by induction.

Let $T$ be a colored rooted tree in which each color appears at most once, and the colors of the children of a node are smaller than the color of the node.
Let $G$ be a greedily colored graph, and let $v$ be a vertex whose color is the same as the color of the root of $T$. Then we can embed $T$ into $G$ in such a way that the root gets mapped to $v$ and the colors of all nodes match.

If $T$ consists of a single node, this is clear. Otherwise, let $T_1,\ldots,T_m$ be the subtrees rooted at the children of the root of $T$. Since the colors of the roots of $T_1,\ldots,T_m$ are distinct and smaller than the color of the root of $T$, the node $v$ must have distinct neighbors $v_1,\ldots,v_m$ whose colors match the colors of the roots of $T_1,\ldots,T_m$. Inductively, we can embed $T_1,\ldots,T_m$ into $G$. Since all colors in $T$ are distinct, the embeddings are disjoint, and so can be put together to construct the desired embedding of $T$.
To derive your claim from this one, you need to show that every tree of size $k$ can be colored according to the prescriptions of this claim. You can use BFS to accomplish that.