As far as I understand it, the primary way the Federal Reserve decreases the money supply is by selling bonds–the entities buying these bonds give up their cash for them and thus M0 is decreased. However, aren't these bonds eventually settled, thus returning the money plus interest back to these entities and eventually increasing M0? If this is the case, can the Federal Reserve "permanently" decrease M0 and if so how?
Can the Federal Reserve permanently decrease money supply?
Yes it can.
For example, if Fed created extra \$1000 by buying \$1000 US bond or treasury bill in exchange for newly created money, then Fed can always reverse this process by either just waiting for the bond to be repaid. When the face value of bond is being repaid government has to somehow pull \$1000 from the economy and send it back to the Fed. At that point the bond and money are destroyed.
Also, I am not sure if I understand your example. Generally speaking, repaying debt destroys money supply, issuing more debt increases the money supply.
Imagine there is no Federal Reserve. It's easy if you try (because the Fed did not exist prior to about 1914). When the federal government operates in a world without the Fed the Treasury department would collect taxes, fees, and other receipts into commercial bank accounts due to the federal govt called Treasury Tax and Loan Accounts (TTL). The net sale of new Treasury bonds would sweep funds from bank deposit accounts into TTL and the net repayment of bonds would sweep funds from TTL back into bank deposits. If the government uses debt management to offset a deficit or surplus then it would sell bonds to cover the difference between spending and collections into TTL. The spending would increase bank deposits at the same rate that bond sales and collections drain bank accounts so the federal government would not increase or decrease deposits in the aggregate bank when it uses debt management to cover the deficit or dispose of the surplus. To dispose of the surplus the Treasury would just net redeem outstanding Treasuries rather than run up bank balances in its TTL accounts. The float of liquid Treasuries is then generated as an alternative financial asset to deposits which are highly liquid and short term Treasuries are highly marketable securities that keep par with bank deposits.
Suppose the federal government runs a persistent surplus. Then it would retire all outstanding Treasury bonds and be forced to increase its spending to offset collections or increase its bank account balance at the expense of those who transfer their account balance to the federal government on the books of the aggregate bank sector. This is like the King in Robin Hood who taxes the people to store up gold for the Crown. It would be bad public policy for the governments at any level to use tax policy to accumulate a large and growing bank account because that drains the financial savings of other sectors.
When the Fed exists it can buy or sell Treasuries and issue bank reserves also known as federal funds. The Fed should be considered to be the Monetary Authority of the Federal Government. The banks, Treasury, and so-called government-sponsored enterprises clear payments among each other using the liabilities of the Fed known as federal funds. The Treasury then has another account at Fed called the Treasury General Account (TGA) which it can use to spend, or to collect funds on the level of reserves, or transfer funds to TGA from TTL, etc. When the Treasury applies debt management this does not alter reserves or deposits in the aggregate bank sector to a first case approximation. The purpose of debt management by Treasury is to enable Fed to have control over monetary policy, using its balance sheet, without Fed having to increase the volume of its operations to offset the impact of Treasury if it did not use debt management to assist Fed.