Why does GTR not need a higher dimension to describe the bending of spacetime?

At heart it is simply about the geometry you are using.

In the Euclidean plane the angles of a triangle always add up to 180 deg. But draw a triangle on a sphere and they add up to more. For example a triangle drawn from the North Pole, round the equator for a bit and back to the pole again has two angles of 90 deg each, so the polar angle represents the angular excess.

The key is that you don't need a three-dimensional globe. A flatlander who noticed angles getting bigger the larger the triangle, would develop spherical (or elliptic) geometry anyway. We say that Euclidean geometry is intrinsically flat but that spherical geometry is intrinsically curved.

Analogous distortions in Minkowski spacetime lead us to the realisation that it too must be curved.

The questions, which GR wants to answer are all connected to measurements you can do in spacetime. All you can do is measure distances, angles and time passed. If you cannot measure distance through the 4th spatial dimension, then you do not care how exactly is our spacetime embedded in this higher dimensional spacetime. All you need to know, are distances, angles and time passed. All of these are defined strictly in our 4 dimensional spacetime.

Look at this picture:

The bunny is composed from bunch of points and lines connecting neighboring points, which creates triangles. Each triangle tells you what are the distances and angles between neighboring points. In fact, the knowledge of length of every line in the picture is sufficient to answer every question about geometry some 2D physicist living on this bunny could hope to ask (of course in reality there should be infinite amount of infinitely small triangles). And our physicist need not concern himself with 3rd dimension, he only needs to know distances in his 2D space.

The question then is only how to codify this knowledge as best as is possible. Mathematicians came up with two very important machines for that - metric and Riemann curvature tensor, which can be computed from metric.

In your first example, when you are bending sheet of paper, ask yourself what changes does the bend assert on measurements restricted to the sheet itself? If you make it into triangles, the angles remain the same and the distances too. Thus the bend you showed does not actually curve the geometry of the paper at all. You just created extrinsic curvature, but this curvature is inaccessible from the paper. Someone living on the paper thinks it is still as flat as ever.

You could then stretch the paper and this would certainly change the drawn triangles. But this wouldn't still curve the geometry. Stretched paper, is as flat as non stretched one. Triangles changed, but they still obey Euclidean geometry. You can simply view your deformation as simple redrawing of triangles (let us ignore global properties for a while and focus only at small neigborhood of some point of the paper) When you draw a circle, its circumference will be $2pi r$, where $r$ is radius.

Only once you deform the paper in such a way as to make high school geometry formulas fail will you create intrinsic curvature. Take for example a sphere:

Suddenly, the circumference of the blue circle is not $2pi r$. It is $2 pi a$, but the physicist living on the sphere cannot measure this $a$. He thinks $r$ is the radius and thus he will find out that something fishy is going on. The geometry is weird. The space thus must be curved.

First, intrinsic curvature and extrinsic curvature are not the same. When you bend a piece of paper, e.g. into a cylinder, it gains extrinsic curvature, but geometry on the paper is not changed (angles in a triangle, circumference of a circle etc) so it does not gain intrinsic curvature.

It may be possible to mathematically embed spacetime into higher dimensions. At least six dimensions are needed including two time dimensions for even simple cases for which we have solutions, but many more dimensions could be needed for the most general solutions. This would be both conceptually and mathematically difficult (most people think the maths of gtr is hard enough already!), and it is physically unjustified because there aren't any other dimensions into which spacetime can be bent.

Intrinsic curvature is not difficult to understand (at least conceptually), and it needs no concept of bending into higher dimensions. It can be understood in the same way that you see the curvature of the Earth on a flat map, through local scaling distortions of the map. Here is a map of a universe with positive curvature. The central galaxy is not distorted, but greater distortion is seen further from the centre (diagrams from Structures of the Sky more explanation, without maths is given in The Large and the Small)

You can “undo” the scaling distortions on this map by mapping it onto a sphere, showing that the map would be the same whichever galaxy you choose for the centre.

Note that the sphere has no physical meaning. It is just a way of drawing a map. We can also draw maps of expanding spacetime, like this. The galaxies do not get bigger, but the distances between them gets bigger.

Other maps can be used. This one is exactly equivalent, but instead of the universe appearing to expand, galaxies appear to get smaller.