The basic features and multi-dimensional instability of electrostatic (EA) solitary waves propagating in an ultra-relativistic degenerate dense magnetized plasma (containing inertia-less electrons, inertia-less positrons, and inertial ions) have been theoretically investigated by reductive perturbation method and small-k perturbation expansion technique. The Zakharov-Kuznetsov (ZK) equation has been derived, and its numerical solutions for some special cases have been analyzed to identify the basic features (viz. amplitude, width, instability, etc.) of these electrostatic solitary structures. The implications of our results in some compact astrophysical objects, particularly white dwarfs and neutron stars, are briefly discussed.