Existence of d-regular subgraphs in a k-regular graph
Your conjecture is false. There are regular graphs with an even number of vertices yet without a 1-regular subgraph. See this question on Mathematics.

The complement of such a graph gives a counterexample to your claim that you can always add a perfect matching to increase the regularity (when the number of vertices is even).

In the bipartite case, however, your conjecture is true. Any $k$-regular bipartite graph can be decomposed into $k$ perfect matchings. This follows from Hall's theorem.