Se puede hacer en una sola línea con `awk`:

    awk -F : '{
    printf "*******************************\nNombre: %s\nTeléfono: %s\nEdad: %s\n*******************************\n", 
    $1, $2, $3
    }' Agenda.txt

Tomo como separador los dos puntos ":" y lo imprimo `awk` que lo formateará con `printf` tomando como valores lo separado entre los dos puntos y eso lo ubicará en los placeholders `%s`.

El resultado sería algo por el estilo:

	******************************* 
	Nombre: nombre1                 
	Teléfono: telefono1             
	Edad: edad1                     
	******************************* 
	******************************* 
	Nombre: nombre2                 
	Teléfono: telefono2             
	Edad: edad2                     
	******************************* 
	******************************* 
	Nombre: nombre3                 
	Teléfono: telefono3             
	Edad: edad3                     
	******************************* 

O más cercano a lo que pides:

    awk -F : 'BEGIN{
    printf "*******************************\n"
    }
    {
    printf "Nombre: %s\nTeléfono: %s\nEdad: %s\n*******************************\n",
    $1, $2, $3
    }' Agenda.txt

Puesto que la salida es:

    *******************************
    Nombre: nombre1
    Teléfono: telefono1
    Edad: edad1
    *******************************
    Nombre: nombre2
    Teléfono: telefono2
    Edad: edad2
    *******************************
    Nombre: nombre3
    Teléfono: telefono3
    Edad: edad3
    *******************************