This problem reminds me of tension field theory and related problems in studying the shape of inflated inextensible membranes (like helium balloons). What follows is far from a solution, but some initial thoughts about the problem.
First, since you're allowing creasing and folding, by Nash-Kuiper it's enough to consider short immersions
$$\phi:P\subset\mathbb{R}^2\to\mathbb{R}^3,\qquad \|d\phi^Td\phi\|_2 \leq 1$$
of the piece of paper $P$ into $\mathbb{R}^3$, the intuition being that you can always "hide" area by adding wrinkling/corrugation, but cannot "create" area. It follows that we can assume, without loss of generality, that $\phi$ sends the paper boundary $\partial P$ to a curve $\gamma$ in the plane.
We can thus partition your problem into two pieces: (I) given a fixed curve $\gamma$, what is the volume of the volume-maximizing surface $M_{\gamma}$ with $\phi(\partial P) = \gamma$? (II) Can we characterize $\gamma$ for which $M_{\gamma}$ has maximum volume?
Let's consider the case where $\gamma$ is given. We can partition $M_{\gamma}$ into
1) regions of pure tension, where $d\phi^Td\phi = I$; in these regions $M_{\gamma}$ is, by definition, developable;
2) regions where one direction is in tension and one in compression, $\|d\phi^Td\phi\|_2 = 1$ but $\det d\phi^Td\phi < 1$.
We need not consider $\|d\phi^Td\phi\|_2 < 1$ as in such regions of pure compression, one could increase the volume while keeping $\phi$ a short map.
Let us look at the regions of type (2). We can trace on these regions a family of curves $\tau$ along which $\phi$ is an isometry. Since $M_{\gamma}$ maximizes volume, we can imagine the situation physically as follows: pressure inside $M_{\gamma}$ pushes against the surface, and is exactly balanced by stress along inextensible fibers $\tau$. In other words, for some stress $\sigma$ constant along each $\tau$, at all points $\tau(s)$ along $\tau$ we have
$$\hat{n} = \sigma \tau''(s)$$
where $\hat{n}$ the surface normal; it follows that (1) the $\tau$ follow geodesics on $M_{\gamma}$, (2) each $\tau$ has constant curvature.
The only thing I can say about problem (II) is that for the optimal $\gamma$, the surface $M_\gamma$ must meet the plane at a right angle. But there are many locally-optimal solutions that are not globally optimal (for example, consider a half-cylinder (type 1 region) with two quarter-spherical caps (type 2 region); it has volume $\approx 1.236$ liters, less than Joriki's solution).
I got curious so I implemented a quick-and-dirty tension field simulation that optimizes for $\gamma$ and $M_{\gamma}$. Source code is here (needs the header-only Eigen and Libigl libraries): https://github.com/evouga/DaurizioPaper
Here is a rendering of the numerical solution, from above and below (the volume is roughly 1.56 liters).
EDIT 2: A sketch of the orientation of $\tau$ on the surface:
Best Answer
A4 paper measures 210*297mm or 595 X 842 points. For maximum volume we want height and diameter of the cylinder to be equal. The circle(s) diameter will be $d$ and the rectangle will be $dX\pi d$. Suppose we take one circle off the end for now–perhaps we can get two. Then we have two scenarios.
If we place the rectangle lengthwise, we have $d+\pi d=842$. So $d=\frac{842}{1+3.1415926}=203.3$. Since the paper is $595$ points wide, we can get $2$ circles 203.3 points off the end and $2$ rectangles from the main body, each $203.3X638.7$ points.
If we place the rectangle across the paper, we have a max of 595 points or $189.4$ points for $d$.
Suppose, however, that we make the rectangle out of two smaller rectangles. Each diameter and rectangle width would be half the paper width wide: $\frac{595}{2}=297.5$ points. The length of the rectangle after the two halves are joined, end-to-end, would be $297.5*3.1415926=934.6$.
Half this length would be $457.3$ and that would leave $842-457.3-297.5=87.2$ points of waste on the end of the paper. Not bad. Hope this helps.