How do I use lemmas that are probably already proven, but including the proof myself is quicker than looking up a source?

You do need to make some effort to find in the literature a result you think is known, but after that what you propose is common and I feel is fine. I do it sometimes. In such a situation, I tend to say ``the following is probably known, but we include a proof for completeness.''

Even if you find the all your background lemmas in the literature, it might still make the reader's life easier if you include some or all of their proofs. It is really annoying to have to request seven obscure papers by inter-library loan, and then figure out all the different authors' notation, just to fill in a few pages of proofs.

For completeness, no it is not plagiarism to state a theorem and prove it without knowing whether that theorem is available already in the literature.

Plagiarism is the purposeful appropriation of someone else's words, claiming that they are your own.

Perhaps, they may be best classified as 'mathematical folklore'.

Let me suggest that citing it as 'mathematical folklore' would be incorrect. Based on what you have said in the question, you have proven the result (you know it to be true) and you also are not aware of a proof in the literature, although you believe one exists. However attributing a result to folklore typically implies much more than that: that the result is well-known by many people in the field, but that it doesn't have a canonical published proof in the literature. As you aren't an expert in the literature in this area, these statements go beyond what you can claim; you would need to be aware, and not just suspect, that the result is common knowledge.

I believe that if I spend enough time going through articles in minor journals/theses in theoretical CS/applied mathematics, eventually, I will find the statements/proofs of these results.

A common scenario in applied research! My approach in such situations is to somewhat "downplay" the result; for example, don't state it as a theorem, but as a proposition. And don't claim in your introduction or your list of contributions that you have proven a new result; focus on the new application instead, and the theorems are just there for completeness of the formal development or out of necessity. Finally, depending on how much effort you (or a coauthor) has put into searching the literature, either say that it is not known to your knowledge, or that it may be known, but you include a proof here anyway.

If you do all this and word it carefully, I don't think you are crossing any ethical lines by not citing the result. And you are certainly not committing plagiarism just by not being aware of something.