CONCAT used in INDEX causes ERROR: functions in index expression must be marked IMMUTABLE
The deciding factor for Postgres is that the function concat() is defined stable and not immutable in the system catalog pg_proc:

SELECT proname, provolatile, proargtypes, proargtypes[0]::regtype AS argtype, prosrc
FROM pg_proc
WHERE proname = 'concat';

proname | provolatile | proargtypes| argtype | prosrc
--------+-------------+------------+---------+-----------
concat  | s           | 2276       | "any"   | text_concat


The manual on pg_proc.provolatile:


  provolatile tells whether the function's result depends only on its
  input arguments, or is affected by outside factors. It is i for
  "immutable" functions, which always deliver the same result for the
  same inputs. It is s for "stable" functions, whose results (for fixed
  inputs) do not change within a scan.


I also added the argument types of the function ("any") to connect to the answers of @dezso and @jjanes, which deliver the rationale behind the decision to make this function only stable. And the name of the internal function (text_concat).

Here is a related question to illustrate why immutability of index expressions is a sine qua non condition:


Intentionally corrupting an index in PostgreSQL


As for using the operator ||:

    SELECT o.oprname, o.oprleft::regtype, o.oprright::regtype, o.oprcode, p.provolatile
    FROM   pg_operator o
    JOIN   pg_proc     p ON p.oid = o.oprcode
    WHERE  oprname = '||';


 oprname |   oprleft   |  oprright   |     oprcode     | provolatile
---------+-------------+-------------+-----------------+-------------
 ||      | anyarray    | anyelement  | array_append    | i
 ||      | anyelement  | anyarray    | array_prepend   | i
 ||      | anyarray    | anyarray    | array_cat       | i
 ||      | text        | text        | textcat         | i
 ||      | bit varying | bit varying | bitcat          | i
 ||      | bytea       | bytea       | byteacat        | i
 ||      | text        | anynonarray | textanycat      | s
 ||      | anynonarray | text        | anytextcat      | s
 ||      | tsvector    | tsvector    | tsvector_concat | i
 ||      | tsquery     | tsquery     | tsquery_or      | i
 ||      | jsonb       | jsonb       | jsonb_concat    | i


The function to use internally depends on actual data type of operands. The definition of an operator includes the operands' data types in Postgres. 
All of the functions are different and also different from text_concat above. || is just stable as well, when one of the operators is anynonarray. Things are not so trivial behind the curtains.

character varying(256) (like any varchar variant) is binary-coercible to text so function type resolution defaults to text.