I'm guessing that 30 reps is about the maximum push-ups you can do.
For training purposes and if you want to do several sets. You most of the times don't go for the maximum reps in the first set. You intentionally do less to be able to complete your 5 or N sets routine.
If I were you I would cut down the reps and try to start with 20 reps or so and build from there on.
Increasing reps
Personally what helped me increase my rep range was to change my routine every other week or month. For example:
- Normal sets: N reps for M sets.
- Weighted: I would do less reps. Don't take too much weight you can't handle. I would keep the rep range +10.
- Pyramid: You would start with 1 rep for the first set, take a short break, then 2 reps, break, 3 reps and so on. When you hit your limit say 10, you go down, 9, 8, ...2, 1.
- Half pyramid: same as pyramid but without going down. Make sure to really go to the max.
- Modified pyramid: when I got in the higher range reps (+50), instead of increasing my reps by one, I increased them by 2 or by 5. For example: 2, 4, 6, 8 ... 18, 20 or 5, 10, 15, 20 ... 45, 50.
- Max reps every set: you would notice decrease in reps here the more sets you do.
Personally the pyramid routine really helped me a lot: I once noticed a progress of 10 extra reps the next week.
Side note: the numbers may seem arbitrary. They partially are, try to figure out what works out best for you.
About rest time
Some people would say 2-3 minutes for beginners. Some would go boot camp style and suggest 30-60 seconds. Some would take 90 seconds. I personally even go for 5 minutes depending on the situation. Bottom line: it depends on your condition, your goals (and motivation :)). Listen to your body but do try to break the limit.