Do we implement it for proof of concept?
Absolutely. It's very easy to miss vital points if no implementation exists. W3C for instance doesn't even allow protocols to be standardized without reference implementation(s). Furthermore, an implementation may show small improvements as well.
Personally I would require an implementation of all the (minimal) options as well. If there are too many options for that, then the protocol is likely too complicated. In that case the design needs to be simplified or a choice should be made which parts should be part of minimal implementation requirements.
Note that the number of protocol types explodes exponentially with the number of options. E.g. if a protocol contains 3 block-ciphers, 3 key sizes and 3 modes-of-encryption (that can be freely combined) then you already have to implement and test $3 \times 3 \times 3 = 27$ combinations.
To provide an example, I know of a protocol that used AES-128, AES-192 and AES-256 only to find out that there was a problem because 192 is not a multiple of the 128 bit block size of AES.
A reference implementation may also provide clarification where a protocol is not completely clear. In other words, it can be used to find out the intent of the authors of the protocol. If this is the case then obviously the formal description of the protocol should be adjusted in the end.
Do we implement it to support our claim that the protocol is efficient?
This, in my opinion, is less important unless the protocol is designed for applications that require a very precise definition of efficiency on a specific platform. The reason is not that efficiency is not important; The efficiency can however normally be calculated pretty accurately.
Furthermore, efficiency is very implementation specific, so just publishing results for a reference design may not paint a complete picture. Optimizing the reference implementation may also compromise the readability and the chance of errors. Separate implementations for specific platforms are often used instead.
- it is impossible to provide test vectors as well if no reference implementation is provided;
- often only test vectors for octet-aligned data is provided when the protocol or algorithm is defined to operate on bits.