Keyboard shortcut for pasting on the GNOME Terminal

Have you tried using Ctrl + Shift + V

You have to use Ctrl+Shift+V to paste into a terminal. Copy is similar; use Ctrl+Shift+C to copy from a terminal.

Arild's comment explains (edited a bit):

Following tradition, some Ctrl+(letter) shortcuts are mapped to entering control characters in the terminal (see How control characters map to keyboards on Wikipedia). That's why we cannot use them for copy and paste. The shortcuts can be overridden in Edit > Keyboard Shortcuts, but especially Ctrl+C is useful to keep assigned to the control character ETX, which is used to interrupt the current command.

Ctrl+Insert for 'copy', Shift+Delete for 'cut' and Shift+Insert for 'paste' also works on most places, including GNOME terminal.