They are both perfectly grammatical sentences, but mean different things.
You could try to phone his office.
This implies "phoning" might fail. It's like saying "Try to jump over the stream." You might fall in the water, or you might succeed.
The problem here is that "phoning" itself will almost certainly succeed. You will pick up the phone, and dial the number, and at least get a voicemail, if nothing else. You don't need to try to phone, you can definitely phone.
You could try phoning his office.
This implies what you wanted it to imply: that you are trying to reach Fred, and this is one possible solution among many.