Constructing a data structure supporting prioritized key lookup
One approach is to use $d$ binary search trees, one tree per element in $\mathcal{K}$.

The tree for $k \in \mathcal{K}$ stores all items $\hat{x_i} = (p_i, k_i, v_{k_i})$ such that $k_i=k$, keyed on the value $v_{k_i}$.

To insert an item, insert it into the appropriate tree.  This can be done in $O(\log n)$ time.

The lookup operation can be done by searching in each binary tree, and taking the best match.  When searching in the tree for $k \in \mathcal{K}$, you search for the key $y[k]$.  This takes $O(d \log n)$ time.

The successor operation can be implemented similarly to the lookup operation, and also takes $O(d \log n)$ time.

You can speed up the operations to take expected $O(1)$, $O(d)$, and $O(d)$ time (respectively) by replacing each binary search tree with a hash table.