standard sequential algorithm with polylog runtime?
Where each operation is $ O\left(\log^kn\right)$ amortized/expected; I don't know if necessarily $\Theta\left(\log^kn\right)$:


Dynamic graph connectivity algorithms

Poly-Logarithmic Deterministic Fully-Dynamic Algorithms
for Connectivity, Minimum Spanning Tree, 2-Edge,
and Biconnectivity (PDF)
Dynamic graph connectivity in polylogarithmic worst case time (PDF, slides)
Fully Dynamic 2-Edge Connectivity Algorithm in
Polylogarithmic Time per Operation (PDF)
Lists of connectivity problems

Maintaining Dynamic Sequences under Equality Tests
in Polylogarithmic Time (PDF)
Distances and point-sets:


Maintaining the miminal distance of a point set in polylogarithmic time (PDF, $O\left(\log^2n\right)$, Smid)
New techniques for some dynamic closest-point and farthest-point problems ($O\left(\log^D n\right)$ Supowit)
New Techniques For Exact And Approximate Dynamic Closest-Point Problems (PDF, Kapoor, Smid, $O\left(\log^D n \log \log n\right)$, though cites others with just $O(polylog)$)
TOPP 63: Dynamic Planar Nearest Neighbors, lists 3 papers with data structures that have operations that run in $O\left(log^k n\right)$ time
Point location algorithms,
Monotone subdivisions, without fractional cascading, query-time is $O\left(\log^2 n\right)$
Best known algorithms for point-location in higher-dimensions ($\gt 2$) have a trade-off; $O\left(\log n\right)$ query-time has large memory requirements that make them unscaleable. Reducing the memory requirements (for example to $O\left(n\log n\right)$ results in query-times of $O\left(\log^k n\right)$

Efficient Partition Trees (PDF, Matousek, $O\left(\log^2 n\right)$ insertion time)
An Implicit Data Structure For The Dictionary Problem That Runs In Polylog Time (Munro, $O\left(\log^2n\right)$)


There are also many algorithms with polylogarithmic factors; $\tilde {O}(\cdot)$ is notation that is used when hiding polylogarithmic factors. So $O\left(n\log^k n \right)\in\tilde {O}(n)$.