"am done with having lunch" vs "finish having lunch"
- am done with having lunch
The construction of this is OK but it's not very idiomatic. Generally, we'd omit "having", and simply say "Once I am done with lunch" or "Once I am finished eating lunch".
This is fine... I'd probably argue to replace "having" with "eating" - it's more specific and descriptive. "Once I finish eating lunch"
As to which is better of the two, simpler is usually better. The first one reads as being unnecessarily wordy. As a native speaker, I'd likely choose
Once I finish eating lunch
"for getting" vs "to get"
This is pretty much wrong. This construction is very odd in general, likely to some degree because it can be confused with "forgetting". Web examples I've found usually are set phrases using getting, such as "getting ripped" (building muscle) or "getting pregnant".
This is correct. You go to a/the park to get some fresh air.
Use of "me"
Yes, "me" is optional in this case.
Some other issues worth mentioning:
"to get some fresh air walking"
This sounds sort of odd... it sounds like you're making the "fresh air" go for a walk.
I go to a park to get some fresh air while taking a walk.
I go to a park to take a walk and get some fresh air.
This sentence sounds like you're talking about what you do on a daily basis. If so, I recommend adding a frequency word to your statement about going for a walk:
I [often/always/usually/sometimes] go to a park to get some fresh air [. . .]
It's not necessary but it can help the flow a bit.