Can a checking account be advertised as free if we charge a NSF/Overdraft fee?

As far as I have been able to research you are ok to advertise it as free and still charge OD/NSF fees. A bank I worked for had Free Checking and charged OD/NSFs and never had any issues.

Yes. In fact, many banks do charge NSF/OD fees on free accounts because NSF/OD fees are not maintenance or activity fees under Regulation DD and, therefore, do not make an account ineligible to be advertised as "free."

FWIW, I agree.

Is a charge for paper statements considered a monthly service fee? The consumer does have the option for online statements at no charge.

If the product is a single product that gives the option to either have free e-statements or a paper statement for a charge, you can't advertise this product as "free" as the charge for paper statements would be considered a monthly service fee since (at least some) consumers would reasonably expect the fee to be imposed on a regular basis.