Why doesn't an object, despite having a non-zero potential energy stored in it, fall by itself from the elevation? When an object is at a certain height, it has some energy stored in it as we have done some work on it to get it to that height. So when it already has energy, then why doesn't it fall off from the table top onto the ground by itself? Why does it need a slope or a push to fall down the edge? Where does the stored energy stay in the object, and why does it only convert into vertical motion and not horizontal motion? 
 A: This answer is only about 

Where does the stored energy stay in the object, and why does it only convert into vertical motion and not horizontal motion?

because I think your other questions have been well-addressed, but this one has only been answered in highly technical terms that may not have clarified anything for you.
Think about what happens if you try to balance a book on top of a large rubber ball.  No matter how careful you are, after only a short time a little wobble will develop and then the book will tilt down to one side and fall off, and the ball will roll away in the opposite direction.  This is exactly what you are saying ought to happen in the case of a table.  But of course it doesn't happen with a table.
What is the difference?  The ball is round.  When the book wobbles on top of the ball, nothing stops the wobble from getting bigger and bigger until the book falls down.  The table is flat.  Imagine that the book wobbles on top of the table: part of the book would push into the material of the table, and the table would push back, and the wobble would stop.  Physicists call this the difference between unstable and stable equilibrium.
(If you put a very heavy object on a table made of soft wood, it may make a dent in the wood.  That's the table failing to push back as hard as it needed to.)
A: 
[...] when it already has energy, then why doesn't it fall off from the table top onto the ground by itself?

Because it is being held back. It wants to fall straight downwards, but the bookshelf applies a normal force to hold up the book, which is stronger than the downwards force (gravity). Just as the rubber band holds back the spring from elongating, because it is stronger than the string force. This is how energy can be stored, and such energy is called potential energy as you rightfully say.

Why does it need a slope or a push to fall down the edge?

Because, as mentioned above, then the downwards force (gravity) is stronger than the vertical force component that holds it up (that could be friction or alike if we are talking about a sliding object on a sloped hill). If it moves or not is all about Newton's second law of motion:
$$\sum F=ma$$
It will only start moving (acceleration), if forces are not balanced. So when gravity pulls in an object and another force counteracts this, then the object doesn't move, because the sum of forces is zero $\sum F=0$. Only if the counteracting force is not large enough to balance gravity, then the object can start falling.
This is regardless of any stored energy.

Where does the stored energy stay in the object [...]

This is a tricky one, and not easily answered. It is stored in the system of the object and the earth. Or rather, in the systems of every particle constituting the object and the earth. It is stored in the fact that every particle has a wish to move downwards (because of gravity) if allowed.
Two planets pull in each other by gravity because they have mass, and so they both move towards each other. Anything smaller still exerts a gravitational force, but smaller. A book pulls a tiny bit in everything else - and in the earth as well. Do when the earth makes the book accelerate down, the earth is accelerated a tiny, tiny bit upwards to the book as well. This should make clear that potential energy is not stored in the object, because it is a property of both the book and the earth. If the earth was removed suddenly, the potential energy would be gone. It is namely stored in the system so to speak made up of the two of objects that pulls in each other. 
Remember that energy is not a "thing" which can be stored in a tank like water. Energy is a concept that has been invented explain different force phenomena. For example, the potential energy is a term invented to describe the willingness of an object to move somewhere if allowed. That potential energy is stored merely tells us that this object will move, if it can.
Like for other kinds of potential energy (elastic as mentioned before, electric, chemical, magnetic etc). They all simply tell, that for the current system, if the object was located at a specific location, there would be an amount of potential energy stored - if it was at some other location, another amount would be stored. The object will then want to move towards the lower potential if allowed.

[...] and why does it only convert into vertical motion and not horizontal motion?

Gravitational potential energy will only convert into kinetic energy in a vertical motion because this is the only direction gravity pulls. Looking back at Newton's second law of motion above we see that initially all forces are in all directions:
$$\sum F_\textrm{horizontal}=0$$
$$\sum F_\textrm{vertical}=0$$
If suddenly in some situation, gravity (which we know pulls straight downwards) is stronger than whatever force is trying to hold it back, if there is any (maybe we held up a book and counteracted gravity, and now we let go so there is no force to balance gravity any-more), then the forces in the vertical direction only will be unbalanced, and some acceleration $a$ happens in that vertical direction, $$\sum F_\textrm{vertical}=ma$$.
A: It is wrong to think potential energy is stored in the object. The earth pulls the object down, but the object pulls the earth up. They share the potential energy.
The object fails to fall down because the tabletop pushes it up.
The earth fails to fall up because the bottom of the table legs push the earth down.
The table pushes up and down because it is squished a bit and squished things push outwards a bit. So for a moment the object did go down and the earth did go up, but as they moved closer the table got squished and so they moved less and less. They stopped when the table was squished enough to counter the gravitational forces.
Why did I bring that all up? Because your focus on just one object is simply a bias. If you had two equally sized objects and you thought each had the potential energy then you'd get the wrong answer by a factor of two.
Since the earth is so much more massive, and the object and earth gain equal and opposite amounts of momentum, the earth gets way less kinetic energy as they move towards each other. So almost all of the change in potential energy is given to the object as kinetic energy, but only because the object it is so much much smaller.
The potential energy belongs to the system, and it gets shares between the parts when it changes. For gravity it changes when the positions change, so they have to move to release energy to divide up.
And neither can move because that pesky table is in the way. Otherwise they indeed would fall towards each other.
If you wanted the object to move sidewise to fall off the table it needs some sidewise velocity, so it either has to start with that velocity or you need a sidewise force. And gravity attracts, so doesn't point sidewise.
A: The first thing is to note that the gravitational potential energy is associated with both the object and the Earth.
You may think that only the object has the potential energy because when you drop the object you see it accelerate downwards and gain kinetic energy.
At the same time the Earth is accelerating upwards at a rate of $\frac {\text {mass of object}}{\text{mass of Earth}}\times \text{acceleration of object}$ and because the Earth is so much more massive than the object which was dropped you do not feel the Earth rising up.  
It would indeed be a most interesting world if everything went to its lowest potential energy state.
The object on the table certainly has a lower potential energy state when it is on the floor but to allowing to reach that lower energy state it must be given some energy to move from a position where the table is underneath it to a position where there is no table.  You may slide the object across the table and do some work against friction, you may lift the object and carry it across to the edge of the table etc but all of these events require the input of energy which cannot be created spontaneously.  
As to converting to vertical motion that is because the force of gravitational attraction is in that direction but on the way down the object could collide with something and gain a horizontal motion.  That horizontal motion was due to a horizontal force acting on the object during the collision.
A: In the case of the ball on the table, it is in a state of stable equilibrium, where the table is pushing up against the ball to counteract the gravitational force pulling it down. If the table and ball were to be moved to a planet with much stronger gravity, the gravitational force on the ball could be strong enough to break the table and the ball would move to a lower potential energy state. The potential energy would be converted to kinetic energy and to the energy involved in breaking through the table.
A: I want to elaborate on MAFIA's correct and important "potential energy is a property of the whole system". The potential energy is not a property of just one of the involved objects, like the lifted ball. That in our common experience all the potential energy somehow seems to be "attached" to the ball is just a consequence of the very different masses.1 
Let's conduct a mental experiment.
Imagine two bodies, like a ball and earth, without motion relative to each other. For simplicity let's assume that any other masses are far away and have no measurable effect. (Circling around the sun etc. just makes things more complicated, although the concept would still hold.)
Now imagine an "almost magical" string (think nano tubes) which has negligible mass and is attached far far away; if you like, you can imagine god holding it because she is amused by this educational exercise. The ball is suspended by that string a few meters above earth's ground so that it cannot fall.
In this scenario, slowly but surely, the earth will start moving towards that ball, driven by the same attraction which would make the ball fall, were it not suspended. Upon impact the earth would have the same kinetic energy the ball would have if the string had been cut; because of its enormous mass it will just be much slower.
The "system's" energy is stored in the gravitational field, much like the electric field between opposite charges contains the energy used to separate them. The physics are not trivial; there may not even be a generally accepted theory or formula, if google didn't mislead me. One of the more accessible approaches which starts with the structural similarity between gravitational and electric fields is on this NASA page.
In any case, assigning energy to a gravitational field is beyond Newtonian physics, but shouldn't deter anybody as a concept. This is how reality is -- space and time are indeed much more more like n-dimensional, transparent  rubber blocks which twist, warp and vibrate, than like the rigid, impartial  Cartesian reference grid of old.

1 The huge mass difference is misleading in other aspects as well: for example, nobody observing a superball bouncing on a marble floor would conceive the concept of the conservation of momentum, because the earth's motion caused by the ball's impact is imperceptible.
A: Although there are excellent answers, I think a more "simplistic" answer is required to correct your thinking.
If you start with a piece of lead (1 kg) on the floor, grab and lift it 1 meter, it will gain (1 x 9.8 x 1 =) 9.8 J of energy.  If you now open your hand (release it), it will fall by "it self" and hit the ground and "loose" the energy it had stored/gained.  Obviously, if while you are holding it , you slide a table under it, the table now will do the job your hand was doing and hold the lead in place.  If you "remove" the (frictionless) table, the weight will fall "by itself", just like the previous case.  
