Here's a sketch of one solution:
Divide your placement domain into rows, each row the height of a label. (If you have boxes of different vertical sizes this becomes more complicated, but it looks like the majority of items in Pillars of Eternity have very similar heights)
For each row, store a list of labels in that row. Each label knows its center, width, and the target point it's trying to align to.
This lets us greatly simplify the problem into finding a placement in a line, without hitting the full \$n^2\$ complexity of checking against every other label on screen.
When you add a new label, round its target point's vertical position divided by the row height to find which row it "wants" to be in.
Try first to place the label in this row.
With a linear or binary search, you can find the first label in the row that belongs to the right of this one / the last label that belongs to the left (based on their respective target positions). If there's no label that belongs to the left or right, you can treat those constraints as infinite.
Check if there's room to place the label between these limits - shifted to bring you as close as you can to your target position. If so, place the label, and you're done.
If not, compute the minimum penetration depth - how much would the other labels need to slide apart to make room? Hang onto that as a score for the disruptiveness of the placement.
Then check the row above/below in the same way, factoring in the vertical shift from where your label "wants" to be as part of their disruptiveness score. You can repeat this out to a controllable maximum vertical displacement. If you find a placement opportunity below a target disruptiveness score, place it. Otherwise, just pick the lowest score you found out of the rows you checked.
If your chosen placement requires sliding, you iterate over the other labels in the row to the left or right of your newly-placed label, shifting them over by the remaining overlap, until no overlap remains.
This approach is \$O(r \cdot k)\$ per insertion (or \$O(r \cdot \log k + k)\$ if you use binary search), where \$k\$ is the number of items in a single row (so, likely in the range of \$k \approx \sqrt n\$ where \$n\$ is the total number of labels on screen), and \$r\$ is the number of rows you check, which gives you a controllable trade-off between placement quality and search complexity. All the steps can be done with simple interval arithmetic, so you don't need to do any boxcasting along the way.