After no shutdown, does an interface always come up — and what do the %LINK / %LINEPROTO messages tell you?

No. no shutdown only clears the administrative shutdown; the interface also has to be physically connected to another device for Layer 1/2 to come up. The console changed state to up messages confirm that actually happened.

Why no shutdown is not enough on its own:

• no shutdown removes the administratively down state.
• For the physical layer to become active, the interface must also be connected to another device (a switch or another router).
• An enabled but unconnected interface will read down/down in show ip interface brief.

Reading the console messages after no shutdown:

%LINK-3-UPDOWN: Interface GigabitEthernet0/0/0, changed state to up
%LINEPROTO-5-UPDOWN: Line protocol on Interface GigabitEthernet0/0/0, changed state to up

• %LINK ... changed state to up = Layer 1 (physical) is now up.
• %LINEPROTO ... changed state to up = Layer 2 (line protocol) is now up.
• Both messages together mean the interface reached the working up/up state.

Go deeper:

• Cisco IOS (Wikipedia) — the IOS logging facility behind %LINK / %LINEPROTO console messages.
• Router (computing) (Wikipedia) — why a routed interface needs both a physical (L1) and data-link (L2) peer to come up.