If you restate the problem in a slightly different (but equivalent) way, an algorithm becomes more obvious:
There are $n$ parties involved: $n-1$ persons, and one restauarant. Let $p_i$ be the amount of money party $i$ should have after the meal is finished and paid for. For example, if Alice has \$36 and owes \$25, Bob has \$12 and owes \$11, and Carl has \$30 and owes \$25, we say that $p_0$ is the restaurant and have:
$p = (61, 11, 1, 5)$
That is, when the meal is over the restaurant should have \$61, Alice should have \$11, Bob should have \$1 and Carl should have \$5.
Now let $b$ enumerate all of the $m$ bills involved. For example:
$b = (1, 5, 10, 20, 1, 1, 5, 5, 10, 20)$
The denominations of the bills do not matter, but I have chosen denominations of paper US currency for this example because they are familiar.
We are seeking to minimize the number of bills that change hands, so we associate a "cost" with person $i$ leaving with bill $j$ by using a $\{0,1\}$ matrix $C$. Entries of 0 in this matrix indicate which bills each party starts with ($C_{0,j} = 0$ for all $j$ because the restaurant starts with no bills).
Continuing our example:
$$
C = \left[ \begin{array}{cccccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
\end{array}
\right]
$$
indicates that Alice started with \$1, \$5, \$10, \$20, Bob started with \$1, \$1, \$5, \$5, and Carl started with \$10 and \$20.
Again, the goal is to minimize the number of bills that change hands. In other words:
$$
\begin{align}
\text{Minimize:} & \sum_{i=0}^{n-1}{\sum_{j=0}^{m-1}{C_{i,j} x_{i,j}}} \\
\text{subject to:} & \sum_{i=0}^{n-1}{x_{i,j}} = 1 \text{ for } 0 \le j \lt m, \\
& \sum_{j=0}^{m-1}{x_{i,j}b_j = p_i} \text{ for } 0 \le i \lt n, \\
\text{and} & x_{i,j} \ge 0
\end{align}
$$
The first constraint says that the solution can only assign a particular bill to one party, and the second ensures that everyone pays the appropriate amount.
This is the 0,1 INTEGER PROGRAMMING problem and is NP-complete (see [Karp 1972]). The Wikipedia page about linear programming has information on different algorithms that can be used for these types of problems.
There are potentially multiple optimal solutions; by hand the first solution to the example I came up with was:
$$
x = \left[ \begin{array}{cccccccccc}
0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
\end{array}
\right]
$$
which means Alice pays exactly \$5 and \$20, Bob pays exactly \$1, \$5 and \$5, and Carl overpays \$10 and \$20 and then removes a \$5 from the table.
I also used the Mixed Integer Linear Program module of the Sage Math system which has the ability to use different solver backends (GLPK, COIN, CPLEX, or Gurobi). The first solution it gave was
$$
x = \left[ \begin{array}{cccccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
\end{array}
\right]
$$
which is almost the same except that Carl took the "other" $5 that Bob put on the table.
Formulating the problem in this way satisfies all the properties you list (you can extrapolate which bills end up where from $C$ and the solution matrix $x$). The exception is perhaps #4 which was discussed in the comments of the question. It is not clear to me what you would like to do in the situation that there is no feasible solution to the set of linear equations:
Identify a subset of people that can pay the reduced total? Or perhaps a subset of people which could still pay the entire bill, i.e. they pay for their friend.
Your final statement makes it seem like you are interested in the case that the denominations of the bills are fixed, this doesn't change the problem however.
In any case, there is also an $O(1)$ solution in which every person pays with a credit card.
